#include <bits/stdc++.h>
#define loop(i,a,b) for(int i=a;i<=b;i++)
#define ll long long
#define ln '\n'
#define pb push_back
#define mod 1000000007
#define cin f
#define cout g
using namespace std;
ifstream f("frac.in");
ofstream g("frac.out");

ll n,p;
vector<int> v;

void func(ll x){
    int d=2;
    while(x>1){
        bool p=0;
        while(x%d==0)p=1,x/=d;
        if(p)v.pb(d);
        d++;
        if(d*d>x)d=x;
    }
}

ll ok(ll x){
    ll m=v.size(),k=(1<<m),p,nr,ans=0;
    for(int i=1;i<k;i++){
        p=1,nr=0;
        for(int j=0;j<m;j++)if(i&(1<<j))p*=v[j],nr++;
        if(nr%2==1)ans+=x/p;
        else ans-=x/p;
    }

    return x-ans;
}

ll bs(){
    ll st=1,dr=2305843009213693952,ans;
    while(st<=dr){
        ll m=(st+dr)/2,x=ok(m);
        if(x>=p)ans=m,dr=m-1;
        else if(x<p)st=m+1;
    }
    return ans;
}

int main()
{
    cin>>n>>p;
    func(n);
    cout<<bs();

    return 0;
}

/**

6469693230
2 3 5 7 11 13 17 19 23 29


*/