#include <fstream>
#include <vector>
using namespace std;

const long long maxN=12e9;

long long n,p;

vector<long long> divs;

long long countCoprimes(long long x){
    long long lim=1LL<<divs.size();
    long long res=0;

    for(long long mask=0;mask<lim;mask++){
        int sgn=1;
        long long prod=1LL;

        for(int i=0;i<divs.size();i++)
            if(mask&(1LL<<i)){
                sgn*=-1;
                prod*=divs[i];
            }

        res+=x/prod*sgn;
    }

    return res;
}

int main(){
    ifstream cin("frac.in");
    ofstream cout("frac.out");

    cin>>n>>p;
    for(long long d=2;d*d<=n;d++)
        if(n%d==0){
            divs.push_back(d);

            while(n%d==0)
                n/=d;
        }
    if(n)
        divs.push_back(n);

    long long sol;
    long long step=1LL<<60;
    for(sol=0;step>0;step>>=1)
        if(countCoprimes(sol+step)<p)
            sol+=step;

    cout<<sol+1;

    return 0;
}