#include<cstdio>
#include<cmath>
bool c[120006];
int prime[50005];
void ciur()
{
    c[0]=c[1]=1;
    int n=120005,i,j;
    int lim=(int)sqrt((double)n);
    for(i=4;i<=n;i=i+2)
        c[i]=1;
    for(i=3;i<=lim;i=i+2)
        if(!c[i])
            for(j=i*i;j<=n;j=j+2*i)
                c[j]=1;
    int u=0;
    for(i=2;i<=n;i++)
        if(!c[i])
            prime[++u]=i;
}
int u2;
long long fact[20];
void descfactpr(long long n)
{
    int d=1;
    u2=0;
    while(n>1 && prime[d]*prime[d]<=n)
      {
      bool ok=0;
      while(n%prime[d]==0)
        {
        n=n/prime[d];
        ok=1;
        }
      if (ok)
          fact[++u2]=prime[d];
      d++;
      }
    if (n>1)
        fact[++u2]=n;
}
long long pinex(long long x)
{
    long long ans=0;
    int i;
    int ns=1<<u2;
    for(i=1;i<ns;i++)
        {
        int c=i;
        long long p=1;
        int nr=1,cardinal=0;
        while(c)
          {
          if (c&1)
              {
              p=p*fact[nr];
              cardinal++;
              }
          nr++;
          c=c>>1;
          }
        if (cardinal%2==0)
            ans=ans-x/p;
        else
            ans=ans+x/p;
    }
    ans=x-ans;
    return ans;
}
int main()
{
    freopen("frac.in", "r", stdin);
    freopen("frac.out", "w", stdout);
    ciur();
    long long n,p;
    scanf("%lld%lld",&n,&p);
    descfactpr(n);
    long long st=1,dr=1LL<<61,med;
    while(st<=dr)
      {
      med=(st+dr)/2;
      if (pinex(med)>=p)
          dr=med-1;
      else
          st=med+1;
      }
    printf("%lld\n",st);
return 0;
}