#include <iostream>
#include <fstream>
#define P2 2305843009213693952
#define nrd 1100000
using namespace std;

ifstream fin ("frac.in");
ofstream fout ("frac.out");

bool prim[nrd+1];
long long pr[1050000];
long long nrfac, nrpr;
long long sol[2000];

void ciur()
{
    long long i, j;
    for(i=4; i<=nrd; i+=2) prim[i]=1;
    for(i=3; i*i<=nrd; i+=2)if(prim[i]==0) for(j=i*i; j<=nrd; j+=i) prim[i]=1;
    for(i=2; i<=nrd; i++)
    {
        if(prim[i]==0)
        {
            nrpr++;
            pr[nrpr]=i;
        }
    }
}

long long rez(long long x)
{
    long long z=0, nr, prod, i, j;
    for(i=1; i<(1<<nrfac); i++)
    {
        nr=0; prod=1;
        for(j=0; j<nrfac; j++)
        {
            if((i&(1<<j))!=0)
            {
                nr++;
                prod=prod*sol[j+1];
            }
        }

        if(nr%2==1) z=z+x/prod;
        else z=z-x/prod;
    }
    return x-z;
}

int main()
{
    long long n, p, i, ct, st, dr, mij, aux, salvez;
    fin>>n>>p;
    ciur();
    //aflu cati factori primi are n
    ct=1;
    while(pr[ct]*pr[ct]<=n && n>1)
    {
        if(n%pr[ct]==0)
        {
            sol[++nrfac]=pr[ct];
            while(n%pr[ct]==0) n=n/pr[ct];
        }
        ct++;
    }
    if(n!=1) sol[++nrfac]=n;

    //cautarea binara
    st=1;
    dr=100000000000000; //1e14
    while(st<=dr)
    {
        mij=(st+dr)/2;
        aux=rez(mij);
        if(aux>=p) {dr=mij-1; salvez=mij;}
        else st=mij+1;
    }
    fout<<salvez;
}