#include <iostream>
#include <fstream>
#include <cmath>
using namespace std;
long long n,p,fa[50],f, dr=1LL<<61,b[50],s,prod,mij;

void factori(long long n){
    for(int i=2;i*i<=n;i++){
        if(n%i==0){
            fa[++f]=i;
            while(n%i==0)
                n/=i;
        }
    }
    if(n!=1)
        fa[++f]=n;
}

void afla(long long k, long long nr){
    for(int i=k;i<=f;i++){
        prod*=fa[i];
        afla(i+1,nr+1);
        prod/=fa[i];
    }

    if(nr%2)
        s+=mij/prod;
    else if(nr!=0)
        s-=mij/prod;
}
int main()
{
    ifstream f("frac.in");
    ofstream g("frac.out");
    f>>n>>p;
    factori(n);

    long long st=-1;
    while(dr-st>1){
        mij=(st+dr)/2;
        prod=1;
        s=0;
        afla(1,0);
        if(mij<=s+p-1)
            st=mij;
        else dr=mij;
    }

    g<<dr;
    return 0;
}