#include<bits/stdc++.h>
using namespace std;
ifstream fin("frac.in");
ofstream fout("frac.out");
vector<long long>di;
void desc(long long n)
{
    for(long long d=2;d*d<=n;d++)
    {
        if(n%d==0)
        {
            while(n%d==0)
                n/=d;
            di.push_back(d);
        }
    }
    if(n>1)
        di.push_back(n);
}
int main()
{
    long long n,p;
    fin>>n>>p;
    desc(n);
    long long st=1,dr=(1LL<<62),mi,poz;
    while(st<=dr)
    {
        mi=(st+dr)/2;
        long long nr=mi;
        long long cmi=mi;
        for(long long i=1;i<(1<<di.size());i++)
        {
            long long nr=0,ci=i,prod=1,x=0;
            while(ci)
            {
                if(ci%2==1)
                {
                    prod*=di[x];
                    nr++;
                }
                ci/=2;
                x++;
            }
            //cout<<prod<<" ";
            if(nr%2==1)
                mi-=cmi/prod;
            else mi+=cmi/prod;
        }
        if(mi>=p)
        {
            dr=cmi-1;
            poz=cmi;
        }
        else st=cmi+1;
    }
    fout<<poz;
}