#include <iostream>
#include <fstream>
#define LL long long
using namespace std;
ifstream fin("frac.in");
ofstream fout("frac.out");
LL p,n,k,d[11];
LL nr(LL x)
{
    LL r=0;
    for(LL prod,sgn,i=0;i<(1LL<<k);++i)
    {
        prod=sgn=1;
        for(LL j=0;j<=k;++j)
            if((i&(1<<j)) != 0) prod*=d[j], sgn*=-1;
        r+=sgn*x/prod;
    }
    return r;
}
int caut()
{
    LL i,pas=1LL<<60;
    for(i=0;pas;pas>>=1)
        if(nr(i+pas)<p) i+=pas;
    return i+1;
}
int main()
{
    fin >> n >> p;
    for(LL i=2;i*i<=n;++i)
        if(n%i==0)
        {
            d[k++]=i;
            while(n%i==0) n=n/i;
        }
    if(n>1) d[k++]=n;
    fout << caut() << '\n';
    fout.close();
    return 0;
}