#include <stdio.h>

using namespace std;

long long n,p;
long long dp[100];
long long nr=0;

long long f(long long x)
{
    long long k,i,pow=(long long) 1<<nr,prod,pow2,numar=(long long)0,nb;
    for(k=1;k<pow;k++)
    {
        prod=(long long)1;
        nb=(long long)0;
        for(i=(long long)0;i<nr;i++)
        {
            pow2=(long long) 1<<i;
            if(k & pow2) {prod*=dp[i]; nb++;}
        }
        if(nb%2==1) numar+=x/prod;
        else numar-=x/prod;
    }
    return x-numar;
}

long long caut()
{
    long long pow=(long long) 1<<20,sol=0;
    while(pow>0)
    {
        if(f(sol+pow)<p)
            sol+=pow;
        pow>>=1;
    }
    return sol+1;
}

int main()
{
    FILE *in,*out;
    in=fopen("frac.in","r");
    out=fopen("frac.out","w");
    fscanf(in,"%lld%lld",&n,&p);
    long long i,n1;
    n1=n;
    for(i=2;i*i<=n;i++)
    {
        if(n1%i==0)
        {
            dp[nr++]=i;
            while(n1%i==0) n1/=i;
        }
    }
    if(n1>1) dp[nr++]=n1;
    long long rez=caut();
    fprintf(out,"%lld",rez);
    return 0;
}