#include <fstream>
#include <vector>
#include <bitset>
#include <cmath>
#define tip long long
#define PMAX 3000000
#define NP 1000001



using namespace std;

ifstream f("frac.in");
ofstream g("frac.out");

bitset<NP> Ciur;
vector<tip> Primes;
vector<tip> Div;
tip N,P,i,ANS,j,n;
tip Prod[PMAX],Comb;

void GenPrimes();
void GenProd();
tip Bin();
tip Calc(tip);

int main() {
    f >> N >> P;
    n=sqrt(N);
    GenPrimes();
    GenProd();
    g << Bin() << '\n';
    f.close();g.close();
    return 0;
}

void GenPrimes() {
    for (i=2;i<=n;i++)
        if (!Ciur[i]) {
            Primes.push_back(i);
            for (j=i+i;j<=n;j+=i) Ciur[j]=1;
        }
}

void GenProd() {
    tip C=N;
    for (tip i=0;i<Primes.size() && C>1;i++) {
        if (C%Primes[i]==0) {
            Div.push_back(Primes[i]);
            while (C>1 && C%Primes[i]==0) C/=Primes[i];
        }
        if (Primes[i]*Primes[i]>C && C>1) {
            Div.push_back(C);
            C=1;
        }
    }
    C=Div.size();Comb=(tip)(1LL<<C);
    tip Sign,prod,k,c,i;
    for (i=1;i<Comb;i++) {
        Sign=0;prod=1;
        for (k=1,c=0;k<Comb;k<<=1,++c)
            if (i&k) {
                ++Sign;
                prod=1LL*prod*Div[c];
            }
        if (Sign%2==1) Sign=1;
                  else Sign=-1;
        Prod[i]=1LL*Sign*prod;
    }
    return;
}

tip Bin() {
    tip p=1,u=(tip)(1LL<<61),m,Z;
    tip ANS=0;
    while (p<=u) {
        m=p+(u-p)/2;
        Z=Calc(m);
        if (Z==P) ANS=m;
        if (Z>=P) u=m-1;
            else p=m+1;
    }
    return ANS;
}

tip Calc(tip M) {
    ANS=0;
    for (i=1;i<Comb;i++)
        ANS+=M/(Prod[i]!=0?Prod[i]:1);
    return (M-ANS);
}