//#include <iostream>
#include <fstream>
#include <math.h>
#include <vector>
using namespace std;
ifstream ka("frac.in");
ofstream ki("frac.out");

const int SQRT_MAX = 109545;

long long n, p;
bool compus[SQRT_MAX + 1];
vector <int> factori;

int binara()
{
	long long inc = 1, sf = (1LL << 61);
	while(inc < sf)
	{
		long long mij = (inc + sf) / 2;
		long long rez = mij;
		long long t = factori.size();
		for(int i = 1; i < (1 << t); i++)
		{
			long long nr = 0, prod = 1;
			for(int j = 0; j < t; j++)
				if(i & (1 << j))
				{
					prod = 1LL * prod * factori[j];
					nr++;
				}
			if(nr % 2 == 1)
				nr = -1;
			else
				nr = 1;
			rez += 1LL * nr * mij / prod;
		}
		//cout << mij << " " << rez << '\n';
		if(rez < p)
			inc = mij + 1;
		else if(rez > p)
			sf = mij - 1;
		else if(rez == p)
			sf = mij;
	}
	return inc;
}

int main()
{
	ka >> n >> p;
    int t = (int)sqrt(n);
    for(int i = 3; i <= t; i += 2)
		for(int j = i * i; j <= t; j += i)
			compus[j] = true;
	if(n % 2 == 0)
		factori.push_back(2);	
	for(int i = 3; i <= t; i++)
		if(!compus[i] && n % i == 0)
			factori.push_back(i);
	ki << binara();
}