#include <fstream>
#include <vector>
#include <climits>
using namespace std;

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

vector<long long>v;
long long n,p,card;
long long st=1,dr=LLONG_MAX,mij;
int x[20];

void desc(long long x)
{
    if(x%2==0)
    {
        v.push_back(2);
        while(x%2==0)
            x/=2;
    }
    for(long long d=3; d*d<=x; d+=2)
        if(x%d==0)
        {
            v.push_back(d);
            while(x%d==0)
                x/=d;
        }
    if(x>1)
        v.push_back(x);
}

void bt(int k, long long prod)
{
    long long t1,t2;
    for(unsigned i=x[k-1]+1; i<v.size(); i++)
    {
        x[k]=i;
        t1=prod*v[i];
        t2=mij/t1;
        if(k%2==0) card+=t2;
        else
            card-=t2;
        bt(k+1,t1);
    }
}
int main()
{
    bool ok=1;
    fin>>n>>p;
    desc(n);
    x[0]=-1;
    while(st<=dr)
    {
        mij=(st+dr)/2;
        card=mij;
        bt(1,1);
        if(card>p) dr=mij-1;
        else if(card<p) st=mij+1;
        else
            break;
    }

    while(ok)
    {
        ok=0;
        for(const auto& x:v)
            if(mij%x==0)
            {
                ok=1;
                --mij;
                break;
            }
    }
    fout<<mij;

    fin.close();
    fout.close();
    return 0;
}