#include <bits/stdc++.h>
std::ifstream cin("frac.in");
std::ofstream cout("frac.out");
long long n,p,ans,nr;
std::pair<bool,long long>a[1010];
void bck(long long i,long long nra,long long nrf,long long val)
{
    if(nra==nrf)
    {
        a[++n]={nrf%2,val};
        return;
    }
    for(;i<=nr;++i)
        bck(i+1,nra+1,nrf,val*a[i].second);
}
long long raspuns(long long x)
{
    long long ans=x;
    for(long long i=1;i<=n;++i)
    {
        if(a[i].first==true)
            ans-=x/a[i].second;
        else
            ans+=x/a[i].second;
    }
    return ans;
}
int main()
{
    cin>>n>>p;
    for(long long d=2;d*d<=n;++d)
    {
        if(n%d==0)
        {
            a[++nr]={true,d};
            while(n%d==0)
                n/=d;
        }
    }
    if(n!=1)
        a[++nr]={true,n};
    n=nr;
    for(long long i=2;i<=nr;++i)
        bck(1,0,i,1);
    long long b=1,e=((1LL*1)<<61)+2;
    while(b<=e)
    {
        if(raspuns((b+e)/2)<p)
            b=(b+e)/2+1;
        else
            e=(b+e)/2-1;
    }
    cout<<b;
    return 0;
}