#include <stdio.h>
#include <math.h>

#define DIM 100000

long long V[DIM];
long long n,P,p,u,i,j,mid,m,rn;

long long diviz (long long n) {
	long long dm = (1<<m)-1,p,nr,rez = 0;
	for (long long i = 1; i<=dm; i++) {
		p = 1;nr = 0;
		for (j=0;j<m;j++)
			if (i&(1<<j)) {
				p*=V[j+1];
				nr++;
			}
		if (nr%2==1)
			rez+=(n/p);
		else
			rez-=(n/p);
	}
	return n-rez;
			
}


int main(){
	FILE *f = fopen("frac.in","r");
	fscanf(f,"%lld %lld",&n,&P);
	fclose(f);
	
	rn = (long long)sqrt(n);
	for (i=2;i<=rn;i++)
		if (n%i == 0) {
			V[++m] = i;
			while (n%i==0) 
				n/=i;
		}
	if (n!=1)
		V[++m] = n;
	
	p = 1; u = (1LL<<60)-1;
	while (p<=u) {
		mid = p+(u-p)/2;
		if (diviz(mid)<P)
			p = mid+1;
		else
			u = mid-1;
	}
	FILE *g = fopen("frac.out","w");
	fprintf(g,"%lld",p);
	fclose(g);
	
	return 0;
}