#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; //numarul de factori primi ai lui N

long long funct(long long x) //numarul de numere <=x care sunt prime cu N (adica nu au divizori primi comuni)
{
    long long rezultat=x;
    for(int i=1;i<=(1<<nd)-1;i++)
    {
        int k,c=0;
        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; //se scad numerele divizibile cu produs de nr impar de factori
        else
            rezultat=rezultat+x/prod; //se aduna celelalte
    }
    return rezultat;
}


int main()
{
    f>>N>>P;
    int rad=sqrt(1.0*N);
    long long rasp;
    if (N%2==0)
    {
        d[nd++]=2; //d=vectorul factorilor primi
        while(N%2==0)
            N/=2;
    }
    for(int divizor=3;divizor<=rad;divizor=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;
}