#include <iostream>
#include <string>
#include <stdlib.h>
#include <assert.h>
#include <time.h>
#include <algorithm>
#include <vector>
#include <cstdio>
#include <cstring>
#include <fstream>
#include <queue>
#include <cstdlib>
#include <iomanip>
#include <cmath>
#include <stdarg.h>
#include <stdio.h>
#include <set>
using namespace std;
//#include <unordered_map>
#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 n, p, nPrime[MAX_PRIM], nrPrime;
bool primes[200000];

int IsPrime (unsigned long long int n)
{
	if (n == 1)
		return 0;
	for (unsigned long long int i = 2; i <= sqrt ( (double)n ); i++)
	{
		if ( n % i == 0)
			return 0;
	}
	return 1;
}

void GeneratePrimes ()
{
	memset (primes, true, sizeof(primes));
	for (long long int i = 2; i < MAX_PRIM; i++)
	{
		if ( primes[i] == true )
			for (long long int j = i * i; j < MAX_PRIM; j += i)
				primes[j] = false;
	}
}

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

unsigned long long int IsGood ( unsigned long long int Proposed ) // PINEX
{
	unsigned long long int nrNotPrime = 0;

	bool bites[MAX_PRIM]; int indice = 0;
	memset ( bites, false, sizeof(bites) );
	unsigned long long int limit = pow ( (double) 2, (int) nrPrime), divs[MAX_PRIM];

	for (int i = 1; i < limit; i++)
	{
		unsigned long long int nr = i, g = 1;
		for (unsigned long long int j = 0; j < nrPrime ; j++)
		{
			bites[j] = nr & 1;
			nr >>= 1; 
		}
		unsigned long long int nrBiti = 0;
		for (unsigned long long int z = 0; z < nrPrime; z++)
		{
			if ( bites[z] )
			{
				nrBiti++;
				g *= nPrime[z];
			}
		}
		g = Proposed / g;
		nrNotPrime += g * (nrBiti & 1 ? 1 : -1);
	}
	return Proposed - nrNotPrime;
}

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 ; D!=1 && i < nrPrime ;i++)
    {
        if (D % nPrime[i] == 0)
        {
			if (Exists(nPrime, nrPrime, nPrime[i]))
                return false;
            while(D != 1 && (D % nPrime[i] ==0))
                D  /= nPrime[i];
        }
         
    }
    return true;    
}


int main()
{
	FILE *f = fopen ("frac.in", "r");
	FILE *g = fopen ("frac.out", "w");
	
	fscanf (f, "%lld %lld", &n, &p);

	GeneratePrimes();
	GenerateNumbers(n);

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



	while ( l <= r )
	{
		unsigned long long int mid = l + ( r - l ) / 2;
		unsigned long long int result = IsGood ( mid );
		
		if ( result == p )
		{
			Answer = mid;
			break;
		}
		else
			if ( result > p )
				r = mid - 1;
			else
				l = mid + 1;
	}

	while ( Answer > 0 && !IsPrimeWith ( n, Answer ) )
		Answer--;

	fprintf (g, "%lld\n", Answer);
	return 0;
}