#include <iostream>
#include <fstream>

using namespace std;

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

long long n,p,st,dr,i,j,divizori[500],nr;

void descompunere(long long n)
{
    if (n%2==0)
        divizori[++nr]=2;
    while (n%2==0)
        n/=2;
    i=3;
    while (n>1)
    {
        if (n%i==0)
        {
            divizori[++nr]=i;
            while (n%i==0&&n>1)
                n/=i;
        }
        i+=2;
    }
}

long long ans(long long m)
{
    long long rez=m;
    for (i=1; i<=nr; i++)
        rez=rez-m/divizori[i];
    long long pow=(1<<nr)-1;
    for (i=3; i<=pow; i++)
    {
        int nrbiti=0;
        long long ci=i;
        while (ci>0)
        {
            if (ci%2==1)
                nrbiti++;
            ci/=2;
        }
        if (nrbiti>1)
        {
            long long aux=m;
            for (j=1; j<=nr; j++)
            {
                if ((1<<(j-1)&i)>0)
                    aux/=divizori[j];
            }
            rez+=aux;
        }
    }
    return rez;
}

int main()
{
    fin >> n >> p;
    descompunere(n);
    st=1;
    dr=9000000000000000000;
    while (st<dr)
    {
        long long m=(st+dr)/2;
        long long k=ans(m);
        if (k==p)
        {
            dr=m;
        }
        else if (k>p)
            dr=m-1;
        else
            st=m+1;
    }
    fout << st << '\n';
}