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

using namespace std;

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

int i,n,p,d,k,V[max_val],Prim[max_val/10],Div[30],j,rad;
long long st,dr,mid,sol1,t;

long long sol(long long x){
	int bit=1,semn=0;
	long long prod=1;
	long long tot=0;
	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;
	
	Prim[++k]=2;
	
	for(i=3;i<=max_val;i+=2){
		if(V[i]==0){
			Prim[++k]=i;
			for(j=i*2;j<=max_val;j+=i)
				V[j]=1;
		}
	}
	
	rad=int(sqrt(n));
	
	for(i=1;i<=k&&Prim[i]<=rad;i++){
		if(n%Prim[i]==0){
			Div[++d]=Prim[i];
			while(n%Prim[i]==0)
				n/=Prim[i];
		}
	}
	
	if(n!=1)
		Div[++d]=n;
	
	
	st=1;dr=max_ll;

	while(st<=dr){
		mid=st/2+dr/2;
		t=sol(mid);
		if(t==p){
			dr=mid-1;
			sol1=mid;
		}
		else{
			if(t>p)
				dr=mid-1;
			else
				st=mid+1;
		}
	}
	
	g<<sol1;
	
	return 0;
}