#include <cstdio>
#include <cmath>
#include <fstream>
using namespace std;
ifstream fi("frac.in");
ofstream fo("frac.out");
int ct;
long long sir[16],n, p;
long long count(long long nr) {
    int mask,cnt,i;
    long long d,ret=0;
    for (mask=0;mask<1<<ct;++mask) {
        cnt=0,d=1;
        for (i=1;i<=ct;++i)
            if ((mask >> (i - 1)) & 1) {
                d*=sir[i];
                ++cnt;
            }
        if (cnt%2==0)
            ret+=nr/d;
        else
            ret-=nr/d;
    }
    return ret;
}
int main() {
    fi>>n>>p;
    int i,rad=(int)sqrt(n);
    long long t=n,st,dr,mij,sol=0;
    for (i = 2; i <= rad; ++i)
        if (t % i == 0) {
            sir[++ct]=i;
            while (t%i==0)
                t/=i;
        }
    if (t!=1) sir[++ct]=t;
    st=1,dr=1;
    dr<<=62;
    while (st <= dr) {
        mij=(st+dr)>>1;
        if (count(mij) >= p) {
            sol=mij;
            dr=mij-1;}
        else
            st=mij+1;
    }
    fo<<sol;
    return 0;
}