#include <fstream>
#include <vector>
#include <bitset>
#define tip long long
#define PMAX 2000000
#define NP 3000010


using namespace std;

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

bool Ciur[NP];
vector<tip> Primes;
vector<tip> Div;
tip N,P;
tip Prod[PMAX];

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

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

void GenPrimes() {
    for (tip i=2;i*i<=N;i++)
        if (!Ciur[i]) {
            Primes.push_back(i);
            for (tip j=i*i;j*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();
    tip Comb=(tip)(1LL<<C),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;
    tip ANS=0;
    while (p<=u) {
        m=p+(u-p)/2;
        if (Calc(m)>=P) u=m-1,ANS=m;
            else p=m+1;
    }
    return ANS;
}

tip Calc(tip M) {
    tip ANS=0,Comb=1<<(Div.size());
    for (tip i=1;i<Comb;i++)
        ANS+=M/Prod[i];
    return (M-ANS);
}