#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 = 2; i <= 400; i++)
		if(!p[i]) {
			for(ll 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];
			D++;
			while(!(B % primes[i]))
				B /= primes[i];
		}

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

ll inline getFactor(ll count) {
	ll p = 1;
	for(int i = 0; i < D; i++) {
		if ( count & 1 )
			p *= -1;
		else
			p *= dividePrimes[i];
		count >>= 1;
	}

	return p;
}

ll inline compute(ll B) {
	ll result = 0;
	ll count = 1 << D;
	while( count ) {
		result += B / getFactor(count);
		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;
	while( l != r ) {
		m = l + (r - l) / 2;
		C = compute(m);

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

	printf("%lld", l);
	return 0;
}