#include<fstream>
using namespace std;
ifstream f("frac.in");
ofstream g("frac.out");
long long n,p;
int div[16],k;
void factoriprimi(long long x){
long long i;
for(i=2;i*i<=x;i++){
if(x%i!=0) continue;
div[k++]=i;
while(x%i==0){
x/=i;
}
}
if(x!=1) div[k++]=x;
}
//Anastasia nu imi copia sursa,te rog
bool solutie[16];
long long produs[1<<15],nr;
void pre(){
long long q=0,sum=1;
for(int i=1;i<=k;i++)
if(solutie[i]){
q++;
sum*=(long long)div[i];
}
if(q%2) sum*=-1;
produs[nr++]=sum;
}
void inapoi(int p){
if(p>k){
pre();
return;
}
solutie[p]=0;
inapoi(p+1);
solutie[p]=1;
inapoi(p+1);
}
long long suma(long long x){
long long s=0;
for(int i=1;i<=nr;i++)
s+=x/produs[i];
return s;
}
long long lookfor(long long x){
long long i,pas=(long long)(1)<<61;
for(i=0;pas!=0;pas>>=1)
if(suma(i+pas)<x)
i+=pas;
return i+1;
}
int main(){
f>>n>>p;
factoriprimi(n);
inapoi(1);
g<<lookfor(p);
return 0;
}