#include <cstdio>
#include <cstring>

using namespace std;

long long n, i, j, p, m, f[30], nr, q, l, sol, ad;

int v[30];


void desc(long long n) {

	long long d=3;
	
	if ( n%2 == 0 ) {
		nr=1; f[1]=2;
		while ( n%2 == 0 )
			n/=2;
	}

	while (n>1) {
		while ( (n%d) && (d*d <= n) )
			d++;

		if (d*d>n) {
			nr++; f[nr]=n;
			break;
		}
		nr++;
		f[nr] = d;

		while ( n%d == 0 )
			n/=d;
	}

}


long long boom(long long x) {
	int i, p, s, j, rez=0;

	memset(v, 0, sizeof(v));
	v[nr]=1;

	if (x == 1)
		return 1;

	for (i=1; i< (1<<nr); i++) {
		s=0;p=1;

		for (j=1; j<=nr; j++) {
			s+=v[j];
			if (v[j] == 1)
				p=p*f[j];
		}

		if (s%2==0)
			rez-= (x/p);
		else
			rez+= (x/p);

//		printf("%d %d %d\n", s, p, rez);

		j=nr;
		while (v[j] == 1) {
			v[j]=0;
			j--;
		}
		v[j]=1;

	}

	return (x-rez);

}

void bsearch(long long l, long long r) {
	long long m = (l+r) / 2, rez;

	rez = boom(m); 
//	printf("%lld %lld\n\n", m, rez);

	if (l>r)
		return;
	
	if ( (rez == p) && ( boom(m-1) < p ) ) {
		sol=m;
		return;
	}

	if ( rez < p )
		bsearch(m+1, r);
	else
		bsearch(l, m-1);
}


int main() {
	freopen("frac.in", "r", stdin);
	freopen("frac.out", "w", stdout);

	scanf("%lld%lld", &n, &p);

	desc(n);

	l=(long long) 1 << (long long) 61;

//	printf("%lld\n", l);

	bsearch(1, l);

	printf("%lld\n", sol);

	return 0;
}