#include <iostream>
#include <fstream>
#include <cmath>

using namespace std;

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

long long d[12],N,P;
int nd;

long long funct(long long x) //numarul de numere <=x care sunt prime cu N
{
    long long rezultat=x;
    for(int i=1;i<=(1<<nd)-1;i++)
    {
        int k,c=0; //numarul de biti al lui i
        long long prod=1;
        for(k=0;k<nd;k++)
            if((i&(1<<k))!=0) //daca bitul k este 1 adica daca iau in calcul divizorul prim k
                {prod=prod*d[k]; c++;}
        if(c%2==1)
            rezultat=rezultat-x/prod;
        else
            rezultat=rezultat+x/prod;
    }
    return rezultat;
}


int main()
{
    f>>N>>P;
    int rad=sqrt(1.0*N);
    long long rasp;
    if (N % 2 == 0)
    {
        d[nd++] = 2;
        while (N%2 == 0)
            N/=2;
    }
    for (int divizor = 3; divizor <= rad; divizor += 2)
        if (N % divizor == 0)
        {
            d[nd++] = divizor;
            while (N%divizor == 0)
                N/=divizor;
        }
    if (N != 1)
    {
        d[nd++] = N;
    }
    long long st=0,dr=1LL<<61;
    while(st<=dr)
    {
        long long m=(st+dr)/2;
        if(funct(m)>=P)
            {rasp=m; dr=m-1;}
        else
            st=m+1;
    }
    g<<rasp;
    f.close(); g.close();
    return 0;
}