#include <bits/stdc++.h>

using namespace std;
ifstream fin("frac.in");
ofstream fout("frac.out");
long long i,nr,j,n,prim[100];
long long verif( long long  x)
{
    long long nn=(1LL<<nr);
    long long  m=nr;
    long long rez=x;
    for(j=1; j<nn; j++)
    {
        long long  nrc=0;
        long long   pp=1;
        for( long long  k=0; k<m; k++)
        {
            if(j&(1LL<<k))
            {
                nrc++;
                pp=pp*prim[k+1];
            }
        }
        if(nrc%2==1)rez=rez- x/pp;
        else rez+=x/pp;
    }
    return rez;
}
int main()
{
    long long n,p;
    fin>>n>>p;
    if(n%2==0)prim[++nr]=2;
    while(n%2==0)
    {
        n=n/2;

    }
    i=3;
    while(i<=n)
    {
        if(n%i==0)
        {
            prim[++nr]=i;
            while(n%i==0)n=n/i;
        }
        i+=2;
    }
    if(n>1)
    {
        prim[++nr]=n;
    }
    long long  st=1;
    long long dr=(1LL<<61);
    while(dr-st>1)
    {
        long long mij=st+(dr-st)/2;
        if(verif(mij)>=p)dr=mij-1;
        else st=mij+1;
    }
    fout<<st;
    return 0;
}