#include<stdio.h>
#include<math.h>
#define fin "frac.in"
#define fout "frac.out"
#define NMAX 1000000000L
unsigned long long n,p,tmp,desc[1000],st=1,dr;
int x[100];
FILE *in,*out;

void desc_f(long long a) {
long long i,lim;
	
	lim=(long long)sqrt(a);

	i=2;

	while (a!=1 && i<=lim) {
		
		if (a%i==0) { 

			while (a%i==0) a/=i;

			desc[++desc[0]]=i;

			++i;
		}

		else ++i;
	}	
	
	if (a!=1) desc[++desc[0]]=a;
}

void go(int i,unsigned long long a) {
int val,j;
unsigned long long aux;
	for (val=x[i-1]+1;val<=desc[0];++val) {

		x[i]=val;
		aux=1;
		for (j=1;j<=i;++j) aux*=desc[x[j]];
			
		if (i%2) tmp=tmp+(a/aux); 
		
		else tmp=tmp-(a/aux);

		go(i+1,a);
	}


}

int main() {
register unsigned long long m,nr1,nr2;

	in=fopen(fin,"r"); out=fopen(fout,"w");

	fscanf(in,"%lld%lld",&n,&p);

	desc_f(n);

	st=1; dr=1000000000*1000000000; //1000000000L*100000000L;
	fprintf(out,"%lld\n",dr);

	while (1) {
		
		m=(st+dr)/2;

		if (st>dr) break;
			
		tmp=0; go(1,m);   nr1=m-tmp; 
		tmp=0; go(1,m-1); nr2=(m-1)-tmp;
	
		if (nr1==p && nr2<p) break ;

		else 
			if (p<=nr1) dr=m-1;
			
			else st=m+1;
	}
	
	fprintf(out,"%lld\n",m);
	
	fclose(in); fclose(out);

	return 0;
}