#include <fstream>
using namespace std;
ifstream fin("frac.in");
ofstream fout("frac.out");
const long long nr=100000000000000000;
long long v[100000], w[100000], sp[100000];
long long func(long long x, long long imp, long long semn, long long num, long long p)
{
    if(x==p+1)
    {
        return semn*num/imp;
    }
    return func(x+1, imp, semn, num, p)+func(x+1,imp*v[x],-(semn),num, p);
}
int main()
{
    long long n, p, ii=0, sum=0;
    fin >> n >> p;
    if(n%2==0)
    {
        ii++;
        v[ii]=2;
        while(n%2==0&&n>1)
        {
            n/=2;
        }
    }
    long long k=3;
    while(n>1)
    {
        if(n%k==0)
        {
            ii++;
            v[ii]=k;
            while(n%k==0)
            {
                n/=k;
            }
        }
        k+=2;
    }
    long long st=1, dr=nr, mid, sol;
    while(st<=dr)
    {
        mid=(st+dr)/2;
        if(func(1LL, 1LL, 1LL, mid, ii)>=p)
        {
            dr=mid-1;
            sol=mid;
        }
        else
            st=mid+1;
    }
    fout << sol;
    return 0;
}