#include<fstream>
#include<string.h>
#define max_ll (1LL<<62)
 
using namespace std;
 
ifstream f("frac.in");
ofstream g("frac.out");
 
long long n,p,d,Div[30],j;
long long st,dr,mid,sol1,t,i;
 
long long sol(long long x){
    long long bit=1,semn=0;
    long long prod=1;
    long long tot=0;
    long long i;
    while(bit!=(1<<d)){
		
        semn=0;prod=1;
		
        for(i=0;i<d;i++){
            if(((bit>>i)&1)==1){
                prod*=Div[i+1];
                semn++;
            }
        }
		
        if(semn%2==0)
            tot-=x/prod;
		
        else
            tot+=x/prod;
		
        bit+=1;
    }
	
    return x-tot;
	
}
 
int main(){
	
    f>>n>>p;
	
    for(i=2;i*i<=n;i++){
        if(n%i==0){
            Div[++d]=i;
            while(n%i==0)
                n/=i;
        }
    }
	
    if(n>1)
        Div[++d]=n;
	
	
    st=1;dr=max_ll;
 
    while(st<=dr){
        mid=(st+dr)/2;
        sol(mid);
        if(sol(mid)>=p){
            dr=mid-1;
            sol1=mid;
        }
        else
            st=mid+1;
    }
	
    g<<sol1;
	
    return 0;
}