#include <stdio.h>
#define dim 20

long long n, p, v[dim];

long long calc(long long nr) {
	long long i, j, res=0, ct=0, mul;
	for (i=1; i<(1<<v[0]); ++i) {
		ct=0;
		mul=1;
		for (j=0; j<v[0]; ++j)
			if (i&(1<<j)) {
				ct++;
				mul*=v[j+1];
			}
		if (ct&1) res+=nr/mul;
		else res-=nr/mul;
	}
	return nr-res;
}

int main() {
	long long i, l, r, m, ct, sol;
	freopen("frac.in", "r", stdin);
	freopen("frac.out", "w", stdout);
	
	scanf("%lld %lld\n", &n, &p);
	
	if (!(n&1)) {
		while (!(n&1)) n/=2;
		v[0]=1, v[1]=2;
	}
	for (i=3; i*i<=n; i+=2)
		if (!(n%i)) {
			while (!(n%i)) n/=i;
			v[++v[0]]=i;
		}
	if (n>1) v[++v[0]]=n;
	
	l=1, r=100;
	while (l<=r) {
		m=(l+r)/2;
		ct=calc(m);
		if (ct==p) sol=m;
		if (ct<p) l=m+1;
		else r=m-1;
	}
	
	printf("%lld\n", sol);
	
	return 0;
}