#include <fstream>
using namespace std;
ifstream fin("frac.in");
ofstream fout("frac.out");
const int nr=100000000000000000;
long long v[100000], w[100000], sp[100000];
int func(int x, int imp, int semn, int num, int 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;
        }
    }
    int 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=100, mid, sol;
    while(st<=dr)
    {
        mid=(st+dr)/2;
        if(func(1, 1, 1, mid, ii)>=p)
        {
            dr=mid-1;
            sol=mid;
        }
        else
            st=mid+1;
    }
    fout << sol;
    return 0;
}