#include <cstdio>
#include <cstdlib>
#include <vector>

using namespace std;

#define bit(i, x)	(((i) >> x) & 1)
#define pb		push_back

vector< long long > Diviz;
long long N, P;

void get_divs( long long x ) {
	int i;
	for (i = 2; i <= 1000000 && i <= x; ++ i) {
		if (x % i == 0)
			Diviz.pb(i);
		while (x % i == 0)	x /= i;
	}
	if (x > 1)
		Diviz.pb(x);
}

long long get_rez(int now[], int M, long long C){
	long long Numar = 1;
	int i, k = 0;
	for (i = 0; i < M; ++i)
		if (now[i] == 1){
			Numar = 1LL * Numar * Diviz[i];
			++k;
		}
	if (k % 2 == 1)
		return C / Numar;
	else
		return -1LL * (C / Numar);
}
long long solve( long long C ) {
	int M = Diviz.size(), i, j, now[200];
	long long Nr = 0;
	
	for (i = 1; i < ( 1 << M ); ++i){
		for (j = 0; j < M; ++j)
			now[j] = bit(i, j);
		Nr += get_rez(now, M, C);
	}
	return C - Nr;
}

void search( long long l, long long r, long long P ) {
	long long m;
	while (l < r) {
		m = (l + r) / 2;
		if (solve( m ) < P)
			l = m + 1;
		else
			r = m;
	}
	
	printf("%lld\n", l);
}
int main( ) {
	int i;
#ifndef DEBUG
	freopen("frac.in", "r", stdin);
	freopen("frac.out", "w", stdout);
#endif
	scanf("%lld %lld", &N, &P);

	get_divs( N );	
	solve( 11LL );
	search(1, (1LL << 61), P);
}