#include <fstream>
using namespace std;
ifstream cin("frac.in");
ofstream cout("frac.out");
long long n,p,pr,sol,m;
int d[100];
void back(int k,int last){
    if(k==d[0]+1){
        if((k-1)%2==0)
            sol-=m/pr;
        else
            sol+=m/pr;
    }else{
        if(k!=1)
            if((k-1)%2==0)
                sol-=m/pr;
            else
                sol+=m/pr;
        for(int i=last+1;i<=d[0];i++){
            pr*=d[i];
            back(k+1,i);
            pr/=d[i];
        }
    }
}
long long pinex(long long a){
    sol=0;
    pr=1;
    m=a;
    back(1,0);
    return a-sol;
}
int main()
{
    cin>>n>>p;
    if(n==1){
        cout<<p+1;
        return 0;
    }
    for(long long i=2;i*i<=n;i++)
        if(n%i==0){
            d[++d[0]]=i;
            while(n%i==0)
                n/=i;
        }
    if(n!=1)
        d[++d[0]]=n;
    long long st=1,dr=(1LL<<61);
    while(st<=dr){
        long long mid=(st+dr)/2;
        long long x=pinex(mid);
        if(x<p)
            st=mid+1;
        else
            dr=mid-1;
    }
    cout<<st;
    return 0;
}