#include <fstream>
using namespace std;
ifstream f("frac.in");
ofstream g("frac.out");
long long d[100],nrd;
long long n,tot,numar;


void generateme(int nr,long long k,int nrk)
{
    if (nr<=nrd) {
        generateme(nr+1,k*d[nr],nrk+1);
        generateme(nr+1,k,nrk);
        return;
    }
    if (nrk%2==0)
        tot+=numar/k;
    else
        tot-=numar/k;

}
long long check(long long q)
{
    numar=q;
    tot=0;
    generateme(1,1,0);
    return tot;
}
int main()
{
    long long i,j,p,sol=0;
    f>>n>>p;
    j=2;
    while (n!=1) {
        if (n%j==0) {
            d[++nrd]=j;
            while (n%j==0)
                n/=j;
        }
        else
            if (j*j>n) {
                d[++nrd]=n;
                n=1;
            }
        j++;
    }
    for (i=1LL<<61;i;i/=2)
        if (check(sol+i)<p)
            sol+=i;
    g<<sol+1<<'\n';

    return 0;
}