#include <fstream>
using namespace std;
ifstream fin("frac.in");
ofstream fout("frac.out");

long long n,p;
long long sol;
long long x;

long long nr[16];
long long bk[16];


void bt(int pas,long long& sol,long long prod=1)
{
    if(prod!=1)
    {
        if(pas%2)
            sol-=x/prod;
        else
            sol+=x/prod;
    }
    if(pas==nr[0]+1)
        return;
    for(int i = bk[pas-1]+1;i<=nr[0];i++)
    {
        bk[pas]=i;
        bt(pas+1,sol,prod*nr[bk[pas]]);
    }
}


long long bs(long long val)
{
    long long st = 1;
    long long dr = (1LL<<61);
    long long s = dr;
    while(st<=dr)
    {
        long long mid = (st+dr)/2;
        x=mid;
        sol = 0;
        bt(1,sol);
        sol=mid-sol;
        if(sol >= val)
            dr=mid-1,s=mid;
        else
            st=mid+1;
    }
    return s;
}


int main()
{
    fin>>n>>p;
    for(int d=2;d*d<=n;d++)
    {
        if(n%d==0)
        {
            while(n%d==0)
                n/=d;
            nr[++nr[0]]=d;
        }

    }
    if(n!=1)
        nr[++nr[0]]=n;
    fout<<bs(p);

}