#include <bits/stdc++.h>

using namespace std;

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

long long N,P,R,divp[20];
int nrd,nt;

void divizorip(long long x)
{
    nrd=0;
    if(x%2==0)
    {
        divp[++nrd]=2;
        do
        {
            x/=2;
        }
        while(x%2==0);
    }
    for(long long i=3;i*i<=x;i+=2)
        if(x%i==0)
    {
        divp[++nrd]=i;
        do
        {
            x/=i;
        }
        while(x%i==0);
    }
    if(x>1)
        divp[++nrd]=x;
}

long long calcul(long long x)
{
    long long rez=x;
    for(int i=1;i<nt;i++)
    {
        long long prod=1;
        for(int j=0,p2;(p2=1<<j)<=i;j++)
            if(i&p2)
                prod*=-divp[j+1];
        rez+=x/prod;
    }
    return rez;
}

int main()
{
    f>>N>>P;
    divizorip(N);
    nt=1<<nrd;
    long long p=1;
    long long u=1LL<<61;
    while(p<=u)
    {
        long long m=(p+u)/2;
        if(calcul(m)<P)
            p=m+1;
        else
        {
            R=m;
            u=m-1;
        }
    }
    g<<R;
    f.close();
    g.close();
    return 0;
}