#include<cstdio>
#define ll long long
#define elif else if

ll int n , p , divs[50];
int k;

ll int count ( ll int x ) {
	
	int i , j , counts , sign ;
	ll int act , result = 0;
	
	for( i = 1 ; i < (1 << k) ; ++i ) {
		act = 1 , counts = 0;
		for( j = 0 ; (1 << j) <= i ; ++j )
			if ( i & (1 << j)) {
				act *= divs[j];
				counts++;
			}
		if ( counts & 1 ) 
			sign = 1;
		else
			sign = -1;
		result += 1LL * sign * x / act;
	}
	
return x - result;
}

void solve()
{
	int i , j ;
	ll int lf , rt , mid , aux = n , act , sol;
	
	for( i = 2 ; i * i <= aux ; ++i )
		if ( aux % i == 0 ) {
			for( ; aux % i == 0 ; aux /= i );
			divs[k++] = i;
		}
	if ( aux != 1 ) divs[k++] = aux;
	
	for ( lf = 1 , rt = 1LL << 62 ; lf <= rt ; ) {
		mid = ( lf + rt ) >> 1;
			act = count ( mid ) ;
		if ( act == p ) 
			sol = mid;
		if ( act < p ) lf = mid + 1;
		else rt = mid - 1;
	}

printf("%lld\n",sol);	
}
		

int main()
{
	freopen("frac.in","r",stdin);
	freopen("frac.out","w",stdout);
	
	scanf("%lld %lld",&n,&p);
	
	solve();
return 0;
}