#include <iostream>
#include <fstream>
#define NMAX 1000001
using namespace std;
ifstream f("frac.in");
ofstream g("frac.out");
int nr,v[101];
long long b,p;
bool verificare(long long x)
{
    int i,j,nrc;
    long long prod,rez;
    rez=x;
    for(i=1;i<(1LL<<nr);i++)
    {
        nrc=0;
        prod=1;
        for(j=0;j<nr;j++)
        {
            if(((1LL<<j)&i)!=0)
            {
                nrc++;
                prod=prod*v[j+1];
            }
        }
        if(nrc%2==1)
        {
            rez=rez-x/prod;
        }
        else
        {
            rez=rez+x/prod;
        }
    }
    if(rez>=p)
        return 1;
    else
        return 0;
}
int main()
{
    int i;
    long long st,dr,mij,val;
    f>>b>>p;
    nr=0;
    for(i=2;i*i<=b;i++)
    {
        if(b%i==0)
        {
            nr++;
            v[nr]=i;
            while(b%i==0)
            {
                b=b/i;
            }
        }
    }
    if(b>1)
    {
        nr++;
        v[nr]=b;
    }
    st=1;
    dr=1LL<<60;
    while(st<=dr)
    {
        mij=(st+dr)/2;
        if(verificare(mij)==1)
        {
            val=mij;
            dr=mij-1;
        }
        else
        {
            st=mij+1;
        }
    }
    g<<val;
    return 0;
}