#include <fstream>
using namespace std;
ifstream cin("frac.in");
ofstream cout("frac.out");
long long prime[70000],k=0;
long long MaiMicCaAPrimCuB(long long a) {
        long long ans = 0;
        for(long long mask = 0; mask < (1 << k); mask++) {
                long long cnt = 0,prod = 1;
                for(long long j = 0; j < k; j++) {
                        if((1 << j) & mask) {
                                cnt++;
                                prod *= prime[j];
                        }
                }
                ans += ((cnt & 1) ? -1 : 1) * (a / prod);
        }
        return ans;
}
int main() {
        long long last=0,a,b,st=1,dr=(1LL<<61),mid;
        cin>>a>>b;
        //cout<<a<<" "<<b<<endl;
        for(long long j = 2; j * j <= a; j++) {
                //cout<<a<<" "<<j<<endl;
                if(a % j == 0) {
                        prime[k] = j;
                        k++;
                }
                while(a % j == 0)
                        a /= j;
        }
        if(a > 1) {
                prime[k] = a;
                k++;
        }/*
        //cout<<k<<endl;
        while(st<dr){
                mid=(st+dr)/2;
                //cout<<mid<<endl;
                if(MaiMicCaAPrimCuB(mid)>b)
                        dr=mid-1;
                else if(MaiMicCaAPrimCuB(mid)<b)
                        st=mid+1;
                else if(MaiMicCaAPrimCuB(mid)==b){
                        last=mid;
                        dr=mid-1;
                }
        }*/
        for (long long pas = (1LL << 61); pas > 0; pas >>= 1) {
                if (MaiMicCaAPrimCuB(last + pas) < b) {
                        last += pas;
                }
        }
        cout<<last+1;
        return 0;
}