#include <fstream>
#include <math.h>
#define nmax 500

using namespace std;

ifstream fin("frac.in");
ofstream fout("frac.out");

int v[nmax];
long long nr, d;
long long n, p, m;
long long sol;

void calcul()
{
	int g = n;
	float val = sqrt(g);
	d = 2;
	nr = 0;
	while(g > 1)
	{
		if(g % d == 0)
			v[++nr] = d;
		while(g % d == 0)
			g /= d;
		if(d > val && g > 1)
		{
			v[++nr] = g;
			g = 1;
		}
		if(d == 2) d+=1;
		else d+=2;
	}
}

int pinex()
{
	int q, p;
	int rez = 0;
	for(long long i = 1; i < (1 << nr); ++ i)
	{
		q = 0;
		p = 1;
		for(long long j = 0; j < nr; ++ j)
			if(i & (1 << j))
			{
				++ q;
				p = p * v[j+1];
			}
		if(q & 1)
			rez += m/p;
		else rez -= m/p;
	}
	return m-rez;
}

int main()
{
	long answer = 0;
	long long st, dr;
	fin >> n >> p;
	st = 1;
	dr = (long long) 1 << 61;
	calcul();
	while(st <= dr)
	{
		m = (st + dr) / 2;
		if(pinex() >= p)
		{
			// fout << answer << "\n";
			dr = m-1;
			answer = (long long) m;
		}
		else
			st = m+1;
	}
	fout << answer << "\n";
	return 0;
}