#include <fstream>
#include <vector>
using namespace std;

inline int nrBiti(long long);
long long solve(long long, long long);
long long ired(long long);

int main(void) {
	long long n, p;
	ifstream fin("frac.in");
	fin >> n >> p;
	fin.close();
	
	ofstream fout("frac.out");
	fout << solve(n, p);
	fout.close();
}

inline int nrBiti(long long x) {
	int nr = 0;
	while(x != 0) {
		++nr; x &= x - 1;
	}
	return nr;
}

vector <long long> prime;
vector <long long> coef;

long long solve(long long n, long long p) {
	if(n % 2 == 0) prime.push_back(2);
	while(n % 2 == 0) n /= 2;
	for(int i = 3; i <= n; i += 2)
		if(n % i == 0) {
			prime.push_back(i);
			while(n % i == 0) n /= i;
		}
	
	for(long long i = 1; i < (1LL << prime.size()); ++i) {
		long long prod = (nrBiti(i) % 2 == 1 ? -1 : 1);
		for(int j = 0; (1LL << j) <= i; ++j)
			if(((1 << j) & i) != 0)
				prod *= prime[j];
		coef.push_back(prod);
	}
	
	long long step = 1LL << 60, rasp;
	for(rasp = -1; step != 0; step >>= 1)
		if(rasp + step < (1LL << 61) && ired(rasp + step) < p)
			rasp += step;
	return rasp + 1;	
}

long long ired(long long x) {
	long long rasp = x;
	for(int i = 0; i < coef.size(); ++i)
		rasp += x / coef[i];
	return rasp;
}