#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

ll n,k;
ll res;
ll ral;

vector<ll>p;

void bkt(int id,int sgn,ll val)
{
        if(id==p.size())
        {
                res+=sgn*(ral/val);
        }
        else
        {
                bkt(id+1,sgn,val);
                bkt(id+1,-sgn,val*p[id]);
        }
}

ll krr(ll x)
{
        res=0LL;
        ral=x;
        bkt(0,1,1);
        return res;
}

int main()
{
        freopen("frac.in","r",stdin);
        freopen("frac.out","w",stdout);
        ll n,k;
        cin>>n>>k;
        for(ll i=2;i*i<=n;i++)
        {
                bool egor=0;
                while(n%i==0)
                {
                        egor=1;
                        n/=i;
                }
                if(egor)
                {
                        p.push_back(i);
                }
        }
        if(n>1)
        {
                p.push_back(n);
        }
        ll r=0,pas=(1LL<<60);
        while(pas)
        {
                if(krr(r+pas)<k)
                {
                        r+=pas;
                }
                pas/=2;
        }
        r++;
        cout<<r<<"\n";
        return 0;
}