#include<bits/stdc++.h>
using namespace std;
#define INIT  ios_base :: sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
#define mp make_pair
#define pb push_back
#define ft first
#define sc second
#define ll long long
#define pii pair<int, int>
#define count_bits __builtin_popcount
#define int ll
ifstream fin("frac.in"); ofstream fout("frac.out");
#define cin fin
#define cout fout




int n, p;
vector<int> d;
int s[20];



void back_track(int pos, int m, int sz, int x){
if(pos>=d.size()){return;}
int m0=m*d[pos];
s[sz+1]+=x/m0;
back_track(pos+1, m0, sz+1, x);
back_track(pos+1, m, sz, x);
return;
}




int32_t main(){
INIT
cin>>n>>p;
int n0=n;
for(int i=2; i<=n0; i++){
    if(n0%i==0){
        while(n0%i==0){
            n0/=i;
        }
        d.pb(i);
    }
}


//Cautare binara celui mai mic numar x, copr[x]==p, copr[x]-numarul de numere coprime cu n pana la x, inclusiv x
int l=1, r=((int)(1000*1000)*(1000*1000)*(1000*1000) ), m=(l+r)/2;

while(l<r){
for(int i=1; i<=15; i++){s[i]=0;}
int m=(l+r)/2;
back_track(0, 1, 0, m);
int bad=0;
for(int i=1; i<=15; i++){
    if( (i%2)==1){
        bad+=s[i];
    }
    else{
        bad-=s[i];
    }
}
int cpr=m-bad;

if(cpr>=p){
    r=m;
}
else{
    l=m+1;
}
m=(l+r)/2;
}
cout<<(r+l)/2;


return 0;
}