#include<fstream>
#include<string.h>
#define max_ll (1LL<<62)

using namespace std;

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

int n,p,d,Div[30],j;
long long st,dr,mid,sol1,t,i;

long long sol(long long x){
	int bit=1,semn=0;
	long long prod=1;
	long long tot=0;
	int 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;
}