#include <cstdio>
#include <cmath>
using namespace std;
typedef long long ll;
ll raspuns,produs = 1,x;
ll nr1; 
ll n, p, fct[30], nr;
void back (int k ) {
	int i;
	if(k > nr) {
		if( nr1 % 2 ==0)
			raspuns = raspuns + x / produs;
		else
			raspuns = raspuns - x / produs;
	}
	else
		for(i = 0; i <= 1; ++i) {
			
			if ( i == 1)
				++nr1, produs *= fct[k];
			back( k + 1);

			if( i == 1)
				--nr1, produs /= fct[k];
		}
}
ll rez(ll val) {
	raspuns = 0;
	x = val;
	produs = 1;
	nr1 = 0;
	back(1);
 return raspuns;
}
int main() {
	freopen("frac.in", "r", stdin);
	freopen("frac.out", "w", stdout);
	ll i, j, r, step;
	scanf("%lld %lld", &n, &p);

		for( i = 2 ; i * i <= n; ++i) {	
			if(n % i == 0 )
				fct[++nr] = i;
			while( n % i == 0)
				n/=i;
		}
		if( n > 1)
			fct[++nr] = n;
		step = 1LL << 61;
		for( i = 0; step; step >>= 1)
			if( rez(i + step) <p )
				i = i + step;
	
	printf("%lld \n",i + 1 );

	return 0;
}