#include<bits/stdc++.h>
using namespace std;
int st[105],dd;
long long d[15],mid;
long long dc,n,p;
long long ls,ld,sol;
pair<long long,long long> comb[1<<15];
void add(int p)
{
    long long pr=1;
    long long nr=0;
    for(int i=1;i<=p;i++)
    {
        if(st[i])
        {
            pr=pr*d[i];
            nr=nr+1LL;
        }
    }
    if(!nr) return;
    dc++;
    comb[dc].first=pr;
    comb[dc].second=nr;
}
void bktr(int p)
{
    for(int i=0;i<=1;i++)
    {
        st[p]=i;
        if(p==dd)
        {
            add(p);
        }
            else
        if(p<dd) bktr(p+1);
    }
}
long long f(long long x)
{
    long long el=0;
    for(int i=1;i<=dc && comb[i].first<=x;i++)
    {
        if((comb[i].second%2))
        {
            el=el+(x/comb[i].first);
        }
            else
        el=el-(x/comb[i].first);
    }
    return x-el;
}
int main()
{
    freopen("frac.in","r",stdin);
    freopen("frac.out","w",stdout);
    scanf("%lld%lld",&n,&p);
    for(int i=2;(i*i)<=n && n>1;i++)
    {
        if(!(n%i))
        {
            d[++dd]=i;
            while(!(n%i)) n/=i;
        }
    }
    if(n>1)
    {
        d[++dd]=n;
    }
    bktr(1);
    ls=1;
    ld=1;
    for(int i=1;i<=61;i++) ld<<=1;
    sol=0;
    while(ls<=ld)
    {
        mid=ls+((ld-ls)>>1);
        if(f(mid)>=p)
        {
            sol=mid;
            ld=mid-1;
        }
            else ls=mid+1;
    }
    printf("%lld\n",sol);
    return 0;
}