#include <bits/stdc++.h>
#define int long long
using namespace std;
ifstream fin("frac.in");
ofstream fout("frac.out");
vector<int> divizori;
int cnt_prime(int nr)
{
    int nr1=pow(2,divizori.size()),ncp=0,nr2,p,x;
    for(int i=1;i<nr1;i++)
    {
        x=i;
        p=1;
        nr2=0;
        for(int j=0;j<divizori.size();j++)
        {
            if(x%2==1)
            {
                p*=divizori[j];
                nr2++;
            }
            x/=2;
        }
        if(nr2%2==1)
        {
            ncp+=nr/p;
        }
        else
        {
            ncp-=nr/p;
        }
    }
    return nr-ncp;
}
signed main()
{
    int n,p,d=2;
    fin>>n>>p;
    while(d*d<=n)
    {
        if(n%d==0)
        {
            divizori.push_back(d);
            while(n%d==0) n/=d;
        }
        d++;
    }
    if(n>1) divizori.push_back(n);
    int st=0,dr=pow(2,61);
    while(dr-st>1)
    {
        int mid=(st+dr)/2;
        if(cnt_prime(mid)<p)
        {
            st=mid;
        }
        else dr=mid;
    }
    fout<<dr;
    return 0;
}