#include<bits/stdc++.h>
using namespace std;

ifstream f("frac.in");
ofstream g("frac.out");

long long n,p,d[105],k,sol;

long long c=2305843009213693952;

void generatee(int nrc, int nrtot, long long x, long long mij)
{
    if(nrc<=k)
    {
        generatee(nrc+1,nrtot+1,x*d[nrc],mij);
        generatee(nrc+1,nrtot,x,mij);
        return;
    }
    if(nrtot%2==1)
    {
        sol-=mij/x;
    }
    else
        sol+=mij/x;
}

int main()
{
    int i,j=2;
    f>>n>>p;
    while(n!=1)
    {
        if(n%j==0)
        {
            k++;
            d[k]=j;
            while(n%j==0)
                n/=j;
        }
        if(n<j*j)
        {
            k++;
            d[k]=n;
            n=1;
        }
        j++;
    }
    long long st=1,dr=c,ans=0,val;
    while(st<=dr)
    {
        sol=0;
        long long mij=(st+dr)/2;
        generatee(1,0,1,mij);
        val=sol;
        if(val>=p)
        {
            if(val==p)
                ans=mij;
            dr=mij-1;
        }
        else
            st=mij+1;
    }
    g<<ans;
    return 0;
}