#include <cstdio>

typedef long long ll;

using namespace std;

ll N, P;
bool p[110000];
ll primes[10460], Pr;
int dividePrimes[40], D;

void read() {
	freopen( "frac.in", "r", stdin );
	freopen( "frac.out", "w", stdout );
	scanf("%lld %lld", &N, &P);
}

void inline precomputePrimes() {
	for(int i = 3; i <= 400; i+=2)
		if(!p[i]) {
			for(int j = i * i; j <= 110000; j+=2 * i)
				p[j] = true;
		}

	primes[0] = 2;
	Pr = 1;

	for(int i = 3; i < 110000; i+=2)
		if (!p[i]) {
			primes[Pr] = i;
			Pr++;
		}
}

void inline getDividePrimes(ll B) {
	D = 0;
	for(int i = 0; i < Pr && primes[i] * primes[i]<= B; i++)
		if (!(B % primes[i])){
			dividePrimes[D++] = primes[i];
			while(!(B % primes[i]))
				B /= primes[i];
		}

	if ( B > 1 )
		dividePrimes[D++] = B;
}

ll inline compute(ll B) {
	ll count = 1 << D, p, result = 0;
	while( count ) {
		p = 1;
		for(int i = 0; i < D; i++)
			if( (1 << i) & count)
				p = -p;
			else
				p *= dividePrimes[i];
		result += B / p;
		count--;
	}

	if( result > 0 )
		return result;
	else
		return -result;
}

int main() {
	read();
	precomputePrimes();
	getDividePrimes(N);

	ll l = 1, r = 1l << 61, C = -1, m = 0, sol = -1;
	while( l <= r ) {
		m = r + (l - r) / 2;
		C = compute(m);

		if (C >= P) {
			sol = m;
			r = m - 1;
		}
		else
			l = m + 1;
	}

	printf("%lld\n", sol);
	return 0;
}