#include<stdio.h>
using namespace std;

long long N, P, k, v[20], s[20], sol, val;

void back(long long mij, int n)
{ long long p = 1;
  int nr = 0,i;
	if (n == k+1)
	{
		for(i = 1; i <= k; i++)
			if(s[i]) p *= v[i], nr++;
		
		if(nr%2 == 0 && nr > 0)
			val += mij/p;
		else if (nr % 2 == 1)
			val -= mij/p;
		
		return ;
	}
	
	s[n] = 0; back(mij, n+1);
	s[n] = 1; back(mij, n+1);
}

void cb(long long in, long long sf)
{ 
	long long mij;
	
	while (in <= sf)
	{
		mij = (in + sf)/2;
		
		val = mij;
		back(mij, 1);
		
		if (val >= P)
			sol = mij, sf = mij-1;
		else
			in = mij+1;
	}
}

int main()
{ long long d,n;
  

	freopen("frac.in", "r", stdin);
	freopen("frac.out", "w", stdout);
	
	scanf("%lld%lld", &N, &P);
	
	n = N;
	d = 2;
	k = 0;
	while(d*d <= N && n > 1)
	{
		if(n % d == 0)
		{
			v[++k] = d;
			while(n%d == 0) n /= d;
		}
		d++;
	}
	if(n > 1) v[++k] = n;
	
	cb(1, ((long long)1<<61));
	
	printf("%lld\n", sol);
	return 0;
}