#include <fstream>
#include <cstring>
#include <algorithm>
#include <vector>
#define i64 long long

using namespace std;

ifstream cin("frac.in");
ofstream cout("frac.out");

long long N, P;
const int vmax = int(1e6)  + 2;
int primes[int(1e5) + 2];
char p[vmax/16 + 1];
int K;

void sieve() {
	for(int i = 1;((i*i)<<1) + ((i<<1)) < vmax;i++) {
		if((p[i>>3] & (1<<(i & 7))) == 0) {
			for(int j = ((i*i)<<1) + (i<<1);(j<<1) + 1 < vmax;j += (i<<1) + 1) {
				p[j>>3] |= (1<<(j & 7));
			}
		}
	}
	primes[K++] = 2;
	for(int i = 1;(i<<1) + 1 < vmax;i++) {
		if((p[i>>3] & (1<<(i & 7))) == 0) {
			primes[K++] = (i<<1) + 1;
		}
	}
}

vector<i64> factors;
void factor(i64 b) {
		for(int i = 0;1ll*primes[i]*primes[i] <= b;i++) {
		if(b%primes[i] == 0) {
			factors.push_back(primes[i]);
			do {
				b /= primes[i];
			} while(b%primes[i] == 0);
		}
	}
	if(b > 1) factors.push_back(b);
}

inline i64 f(i64 a) {
	i64 ret = 0;
	int m = (int)factors.size();
	for(int i = 1;i < (1<<m);i++) {
		int num = 0;
		i64 val = 1;
		for(int j = 0;j < m;j++) {
			if((i>>j) & 1) {
				num++;
				val *= factors[j];
			}
		}
		ret += (num & 1 ? 1 : -1)*a/val;
	}
	return a - ret;
}

int main()
{
	cin>>N>>P;
	sieve();
	factor(N);
	i64 ret = 0;
	for(i64 step = 1ll<<60;step > 0;step >>= 1) {
		if(f(ret + step) < P) {
			ret += step;
		}
	}
	cout<<ret + 1;
	return 0;
}