#include <cstdio>
#include <cmath>
using namespace std;
int long long vf, i, PrimeList[110005], M, BList[110005], vfb, NN;
int long long N, P;
bool Ciur[110005];
bool CheckPrime(int long long A){
    int i;
    for(i=1; i<=vfb; i++) if(!(A%BList[i]))return 0;
    return 1;
}
int long long Calculate(int long long A, int long long B){
    int long long d=0; int long long i, p, j, P, S=0, k; vfb=0;
    while(B>1){d++;
        if(!(B%PrimeList[d])){while(!(B%PrimeList[d]))B/=PrimeList[d];
                              BList[++vfb]=PrimeList[d];}
        if(PrimeList[d]>sqrt(B) && B>1) {BList[++vfb]=B; B=1;}
    }
    for(i=1; i<=(1<<vfb)-1; i++){p=i; P=1; k=0;
    for(j=1; j<=vfb; j++){
      if(p&1) {P*=BList[j]; k++;}
      p/=2;
    }
    P=A/P;
    if(k%2)
     S+=P;
     else S-=P;
    }
    return S;
}
void Peridot(){
    int i, j; bool k;
    for(i=2; i<sqrt(N); i++){
        if(!Ciur[i]){for(j=2*i; j<sqrt(N); j+=i)Ciur[j]=1;
                     PrimeList[++vf]=i;

    }
}
}
int main()
{
    freopen("frac.in", "r", stdin);
    freopen("frac.out", "w", stdout);
    scanf("%lld%lld", &N, &P);
    Peridot();
    NN=N;
    if(P==1){printf("1"); return 0;}
    int long long st=1, dr=(1LL<<61);
    int long long mij;
    while(st<dr){
        mij=(dr-st)/2+st;
        M=Calculate(mij, NN);
        M=mij-M;
        if(M==P){break;}
        else if(M>P) {dr=mij-1; continue;}
        else {st=mij+1; continue;}
    }
    while(!(CheckPrime(mij)))mij--;
    printf("%lld", mij);
    return 0;
}