#include <bits/stdc++.h>
using namespace std;
ifstream f("frac.in");
ofstream g("frac.out");
long long n,p,k,sol,st,dr,m,dp[15],z;
long long pr(long long x)
{
    long long y=0,i,j,nrb,pp;
    for(i=1;i<(1<<k);++i)
    {
        nrb=0;
        pp=1;
        for(j=0;j<k;++j)
        {
            if(i>>j&1) {pp*=dp[j+1];nrb++;}
        }
        if(nrb&1) y+=x/pp;
        else y-=x/pp;
    }
    return x-y;
}
int main()
{
    f>>n>>p;///12 5
    long long d=2,i;
    while(n>1)
    {
        if(n%d==0) dp[++k]=d;
        while(n%d==0) n/=d;
        d++;
        if(d*d>n) d=n;
    }
    st=1;
    dr=LLONG_MAX;
    sol=1;
    while(st<=dr)///st=1 dr=10^18
    {
        m=st/2+dr/2;///10^17*5
        z=pr(m);///
        if(z>=p) {dr=m-1;sol=m;}
        else st=m+1;
    }
    g<<sol;
    return 0;
}