#include<iostream>
#include<fstream>
using namespace std;

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

#define ll long long
#define MaxDiv 100
#define mid ((li+ls)/2)

ll N,P,nrDiv;
int Div[MaxDiv];

void descompunere(ll N)
{
    ll a = N;

    for(ll i=2;i*i <= a && N > 1;i++)
        if(N%i == 0)
        {
            Div[++nrDiv] = i;
            for(;N%i == 0;N/=i);
        }

    if(N > 1)
        Div[++nrDiv] = N;
}

inline ll pinex(ll val)
{
    ll Sum = 0,Prod,nr;

    for(int i=1;i<(1<<nrDiv);i++)
    {
        Prod = 1LL;
        nr = 0;

        for(int j=0;j<nrDiv;j++)
            if(i & (1<<j))
                Prod *= Div[j+1], ++ nr;

        if(nr%2)
            Sum += val/Prod;
        else
            Sum -= val/Prod;
    }

    return Sum;
}

inline ll cautBin(ll li,ll ls)
{
    if(li > ls)
        return li;

    //cout << li << " " << ls << "\n";

    ll numar = mid-pinex(mid);

    //cout << mid << " " << numar << "\n";

    if(numar >= P)
        return cautBin(li,mid-1);
    else
        return cautBin(mid+1,ls);
}

int main()
{
    f >> N >> P;

    descompunere(N);

    g << cautBin(2LL,(1LL<<61)-10LL);
}