#include <cstdio>
#define MAX 1000000
#define INF (1<<61)LL
using namespace std;
bool ciur[MAX+1];
int k, prime[MAX+1], st[MAX+1], n;
long long N, P, prod[MAX+1], cmb;
inline int biti(int x)
{
    int nr=0;
    for(int i=0;i<n;++i)
        if((1<<i)&(x))
            nr++;
    if(nr%2==0)
        return -1;
    return 1;
}
inline long long prod_calc(int x)
{
    long long p=1;
    for(int i=0;i<n;++i)
        if((1<<i)&(x))
            p*=st[i+1];
    return p;
}
inline void produse(long long N)
{
    for(int i=1;i<(1<<(n));++i)
        prod[++cmb]=biti(i)*prod_calc(i);
}
void ciuruire()
{
    int prim=2;
    while(prim*prim<=MAX)
    {
        prime[++k]=prim;
        for(int i=prim;i*prim<=MAX;++i)
            ciur[i*prim]=1;
        prim++;
        while(ciur[prim])
            prim++;
    }
    for(int i=prim;i<=MAX;++i)
        if(!ciur[i])
            prime[++k]=i;
    for(int i=1;i<=k && N!=1;++i)
        if(N%prime[i]==0){
            st[++n]=prime[i];
            while(N%prime[i]==0)
                N/=prime[i];
        }
    if(N!=1)
        st[++n]=N;
    produse(N);
}
long long calculeaza(long long A)
{
    long long nr=0;
    for(int i=1;i<=cmb;++i)
        nr+=A/prod[i];
    return A-nr;
}
long long cauta(long long P)
{
    long long r, stg, dr, mij, last;
    stg=1;
    dr=100000000000000LL;
    while(stg<=dr)
    {
        mij=(stg+dr)/2;
        r=calculeaza(mij);
        if(r<P)
            stg=mij+1;
        else if(r>=P){
            dr=mij-1;
            last=mij;
        }
    }
    return last;
}
int main()
{
    freopen("frac.in", "r", stdin);
    freopen("frac.out", "w", stdout);
    scanf("%lld%lld", &N, &P);
    ciuruire();
    printf("%lld", cauta(P));
    return 0;
}