#include <cstdio>
#include <cstring>
#include <iostream>
#include <cmath>

#define MAXD		1500
#define EPSILON		0.0001
#define min(a,b) ( a < b ? a : b)
#define MAX_NUMERE	12000000000 

#define MAX_PRIM	100000

unsigned long long  int	 nPrime[MAX_PRIM], nrPrime;
unsigned long long  int	 N,K,P;
bool			 Prime[200000];


bool IsPrim(unsigned long long  int N )
{
	if (N  < 2 )
		return false;
	for (unsigned long long  int i = 2 ; i <= sqrtf((double)N) ; i++)
		if (N % i == 0)
			return false;
	return true;
}

void GeneratePrims()
{
	memset(Prime,true,sizeof(Prime));
	Prime[0] = Prime[1] = false;

	for (unsigned long long  int i = 2 ; i < MAX_PRIM ; i++)
		if (Prime[i] == true)
			for (unsigned long long  int j = i<<1 ; j < MAX_PRIM ; j += i)
				Prime[j] = false;
}

void GenerateNumbers(unsigned long long  int N)
{
	unsigned long long  int limit = (unsigned long long  int) sqrt((double)N);	
	for (unsigned long long  int i = 2 ; i <= limit ; i ++) 
		if (Prime[i] && (N % i == 0))
		{
			nPrime[nrPrime ++] = i;
			while(N % i == 0)
				N /= i;
		}	
	
	if (IsPrim(N))
		nPrime[nrPrime ++] = N;
		
}

bool Exists(unsigned long long  int v[], unsigned long long  int nr, unsigned long long  int N)
{
	if (nr == 0 )
		return false;

	unsigned long long  int l = 0, r = nr - 1,k;
	while( l <= r )
	{
		k= (l + r) / 2;
		if (v[k] == N )
			return true;
		else	if (v[k] > N)
		{
			if (  ! (k > 0 ) )
				return false;

			r = k -1 ;
		}
		else
			l = k + 1 ;
	}

	return false;
}

//test if N is prime with D
bool IsPrimeWith(unsigned long long  int N,unsigned long long  int D)
{
	bool IsNumberSet[MAX_PRIM];
	memset(IsNumberSet,false,sizeof(IsNumberSet));

	unsigned long long  int divizori = 0,Divs[MAX_PRIM];
	unsigned long long  int i , j ;
	for (i = 0 ; N!=1 && i < nrPrime ;i++) 
	{
		if (N% nPrime[i] == 0)
		{
			Divs[divizori++] = nPrime[i];
			while( N!=1 && (N%nPrime[i] == 0))
				N /= nPrime[i];
		}

	}

	for (i = 0 ; D!=1 && i < nrPrime ;i++)
	{
		if (D % nPrime[i] == 0)
		{
			if (Exists(Divs,divizori,nPrime[i]))
				return false;
			while(D!=1 && (D%nPrime[i] ==0))
				D  /= nPrime[i];
		}
		
	}
	return true;	
}

unsigned long long  int IsGood(unsigned long long  int Proposed)
{
	//if (!IsPrimeWith(N,Proposed))
	//	return false;

	unsigned long long  int nrNotPrime = 0;
	bool Bites[MAX_PRIM];
	memset(Bites,false,sizeof(Bites));

	unsigned long long  int limit = pow((double)2,(int)nrPrime);
	for (unsigned long long  int i = 1 ; i < limit ;i++)
	{
		unsigned long long  int nr = i,p = 1;
		for (unsigned long long  int j = 0 ; j < nrPrime ;j++,nr>>=1)
			Bites[j] = nr & 1;
		
		unsigned long long  int nrBiti = 0 ;
		for (unsigned long long  int j = 0 ; j < nrPrime ; j++)
			if (Bites[j])
			{
				nrBiti ++;
				p *= nPrime[j];
			}

			p = Proposed / p ;

		nrNotPrime += p *(nrBiti & 1 ? 1  : -1 );
	}

	return (Proposed - nrNotPrime );
}

bool verify(unsigned long long int R)
{
	unsigned long long int nrFractie = 0 ;
	
	unsigned long long int iCandidat = 0;
	while(nrFractie < P)
	{
		bool Prim = 0;
		while(!Prim)
		{
			iCandidat ++;
			if (IsPrimeWith(iCandidat,N))
				Prim = 1;
		}

		nrFractie++;
	}

	return (R == iCandidat);
}

int main()
{
	freopen("frac.in","r",stdin);
	freopen("frac.out","w",stdout);
	
	scanf("%lld %lld",&N,&P);
	GeneratePrims();
	GenerateNumbers(N);

	unsigned long long  int l = 1 ;
	unsigned long long  int r = -1;

	unsigned long long int Raspuns = - 1;

	while (l <= r )
	{
		unsigned long long  int k = l + ( r  - l ) / 2;
		
		unsigned long long  int res = IsGood(k);
		if (res == P)
		{
			Raspuns = k ;
			break;
		}
		else if (res > P)
			r = k - 1 ;
		else
			l = k + 1 ;
	}

	while( Raspuns > 0 && !IsPrimeWith(N,Raspuns))
		Raspuns--;


	//bool good = verify(Raspuns);

	printf("%lld\n",Raspuns);
	return 0;
}