#include<fstream>
#include<cstring>
#include<iomanip>
#include<iostream>
#include<queue>
#include<stack>
#include<algorithm>
#include<unordered_map>
#define DN 1005
#define DM 10005
#define M 666013
#define B 10000
#define x first
#define y second
using namespace std;
ifstream fin("frac.in");
ofstream fout("frac.out");
long long n,p,st,dr,mij,a[25],nr,put,s[(1<<20)+5],r[(1<<20)+5],f,nrb;
long long getpoz(long long f)
{
    long long rez=0;
    for(int i=0;i<put;i++)
        rez=rez+s[i]*(f/r[i]);
    return rez;
}
int main()
{
    fin>>n>>p;
    for(int d=2;1LL*d*d<=n;d++)
        if(n%d==0)
        {
            nr++;
            a[nr]=d;
            while(n%d==0)
                n/=d;
        }
    if(n>1)
    {
        nr++;
        a[nr]=n;
    }
    put=(1<<nr);
    for(int i=0;i<put;i++)
    {
        nrb=0;
        r[i]=1;
        for(int j=0;j<nr;j++)
            if((i&(1<<j)))
            {
                nrb++;
                r[i]=r[i]*a[j+1];
            }
        s[i]=1;
        if(nrb%2)
            s[i]=-1;
    }
    st=1;
    dr=1e18;
    while(st<dr)
    {
        mij=(st+dr)/2;
        if(getpoz(mij)>=p)
            dr=mij;
        else
            st=mij+1;
    }
    fout<<st;
}