#include <cstdio>
#include <cstdlib>
#include <ctime>
#include <cmath>
#include <cstring>
#include <algorithm>
#include <vector>
#include <queue>

using namespace std;

long long n, x, y, p, u, mij, k, aux, w, o, e;
long long i, j, q, v[60005], prim[55];
char c[25000];

long long f(long long x)
{
    long long r=0;
    for(long long i=1;i<e;i++)
    {
        long long y=1, nr=0;
        for(long long j=0;j<w;j++)
            if((1LL<<j)&i)
            {
                nr++;
                y*=prim[j+1];
            }
        if(nr&1)
            r=r+(x/y);
        else
            r=r-(x/y);
    }
    return (x-r);
}

int main()
{
    freopen("frac.in", "r", stdin);
    freopen("frac.out", "w", stdout);
    scanf("%lld%lld", &n, &x);
    q=1;v[q]=2;
    for(i=1;(i<<1)+1<=150000;i++)
        if(!(c[i>>3]&(1<<(i&7))))
        {
            v[++q]=(i<<1)+1;
            for(j=((i*i)<<1)+(i<<1);(j<<1)+1<=150000;j+=((i<<1)+1))
                c[j>>3]|=(1<<(j&7));
        }

    w=0;k=0;aux=n;
    while(aux>1)
    {
        k++;
        if(k>q) break;
        o=0;
        while(!(aux%v[k]))
        {
            aux/=v[k];
            o=1;
        }
        if(o==1)
            prim[++w]=v[k];
    }
    if(aux>1) prim[++w]=aux;
    e=1LL<<w;

    p=1;u=1LL<<61;
    y=0;
    while(p<=u)
    {
        mij=p+(u-p)/2;
        if(f(mij)>=x)
        {
            y=mij;
            u=mij-1;
            continue;
        }
        p=mij+1;
    }
    printf("%lld", y);
    return 0;
}