#include<fstream>
#include<algorithm>
#include<cstring>
#include<vector>
#include<string>
#include<queue>
#define abs(x) ((x>0)?(x):(-(x)))
#define max(a,b) ((a)>(b)?(a):(b))
#define min(a,b) ((a)<(b)?(a):(b))
#define ll long long
using namespace std;
ifstream in("frac.in");
ofstream out("frac.out");
ll v[20];int K;
ll N,P;
ll s,pp;
int d[20];
ll prod[20];
int sign(int i){
    return ( i%2==1 ? 1 : -1 );
}
void back(int i){
    if(i<=K){
        for(d[i]=d[i-1]+1;d[i]<=K;d[i]++){
            prod[i]=prod[i-1]*v[d[i]];
            s+=(pp/prod[i])*sign(i);
            back(i+1);
        }
    }
}
ll neprim(ll p){
    s=0,pp=p;
    back(1);
    return s;
}
ll prim(ll p){
    return p-neprim(p);
}
ll caut(){
    ll i=0,pas=(1LL<<61);
    while(pas){
        if(i+pas<=(1LL<<61) && prim(i+pas)<P) i+=pas;
        pas>>=1;
    }
    return i+1;
}
int main(){
    in>>N>>P;
    for(int i=2;i*i<=N;i++){
        if(N%i==0){
            v[++K]=i;
            while(N%i==0) N/=i;
        }
    }
    if(N>1) v[++K]=N,N=1;
    prod[0]=1;
    out<<caut()<<'\n';
    return 0;
}