#include <iostream>
#include <vector>
#include <fstream>
using namespace std;
ifstream f("frac.in");
ofstream g("frac.out");
long long n,p,st=1,dr=(1LL<<61),rez,poz,lim;
vector<long long>divi;

long long fa(long long x) {
    long long rez=x;
    for(int i=1; i<lim; i++) {
        long long k=0,r=1;
        for(int j=0; (1<<j)<=i; j++) {
            if((1<<j)&i) {
                k++;
                r=r*divi[j];
            }
        }
        if(k%2==1) {
            rez-=x/r;
        } else {
            rez+=x/r;
        }
    }
    return rez;
}


int main() {
    f>>n>>p;
    for(long long i=2; i*i<=n; i++) {
        if(n%i==0) {
            divi.push_back(i);
            while(n%i==0) {
                n/=i;
            }
        }
    }
    if(n>1) {
        divi.push_back(n);
    }
    lim=(1<<(divi.size()));
    while(st<=dr) {
        long long mij=(st+dr)/2;
        long long cat=fa(mij);
        if(p<=cat) {
            poz=mij;
            dr=mij-1;
        } else {
            st=mij+1;
        }
    }
    g<<poz;
    f.close();
    g.close();
    return 0;
}