using namespace std;

#include <cstdio>
#include <algorithm>

#define FOR(i,a,b) for(int i=a;i<=b;++i)
#define IN "frac.in"
#define OUT "frac.out"
#define II inline 
#define ll long long
#define VAL_MAX 1LL<<51

ll N,P;
ll bit;
ll stv[1<<12];

II ll number(ll x);
II void scan()
{
	freopen(IN,"r",stdin);
	freopen(OUT,"w",stdout);
	scanf("%lld%lld",&N,&P);
}

II void desc()
{
	ll n = N;
	if((n >> 1) << 1 == n)
		stv[ ++stv[0] ] = 2; 
	for(;(n >> 1) << 1 == n;n >>= 1);
	for(ll i=3;i*i<=n;i+=2)
	{	
		if(N / i * i == n)
			stv[ ++stv[0] ] = i;
		for(;n / i * i == n;n /= i); 
	}	
	if(n > 1) stv[++stv[0]] = n;
}

II ll find()
{
	ll m,Step;
	for(Step = 1;Step <= VAL_MAX;Step <<= 1);
	for(m=1;Step;Step >>= 1)
  		if(m + Step <= VAL_MAX &&  number(m+Step-1) < P)
			m += Step;
	return m;	
}


II void biti(ll i,ll &prod,ll &cate)
{  
	prod = bit = 1;  
    cate=0;  
    for(;i;++bit,i >>= 1)
	{
		if(i & 1)
		{  
            ++cate;  
            prod *= stv[bit];  
        }
	}	
}

 
II ll number(ll x)
{
	ll s(0),prod;  
    ll cate; 
	
    for(ll i=0;i < (1<<stv[0]);++i)
	{  
        biti(i,prod,cate);  
        if(cate & 1)  
            s -= x / prod;  
        else 
			s += x / prod;  
    }  
    return s;  
}	

int main()
{
	scan();
	desc();
	printf("%lld\n", find() );
	return 0;
}