#include <fstream>
using namespace std;

#define Lmax 1000011 
#define Xmax 1001
#define ll long long
#define max(a ,b) ( ( a>b ) ? a : b )

int P,Q,Sol;
ll Ciur[Lmax];

int Co;
struct Descompunere
{ int num;int pwr; }List[Xmax]; 

int main(void)
{
	ifstream F("gfact.in");
	ofstream G("gfact.out");
	
	F>>P>>Q;
	
	if ( ! P%2 )
	{
		List[++Co].num=2;
		while ( ! P%2 )
			P/=2,++List[Co].pwr;
	}
	
	for (int i=3;P>1;i+=2)
		if ( ! P%i )
		{
			List[++Co].num=i;
			while ( ! P%i )
				P/=i,++List[Co].pwr;
		}
	
	for (int i=1;i<=Co;++i)
	{
		int var=List[i].num;
		while ( var < Lmax )
		{
			for (int j=var;j<=Lmax;j+=var)
				++Ciur[j];
			var*=List[i].num;
		}
		
		int j;
		for (j=1;j<=Lmax && Ciur[j-1]< (ll) List[i].pwr * Q;++j)
			Ciur[j]=Ciur[j-1]+Ciur[j];
		
		Sol=max(j-1,Sol);
	}
	
	G<<Sol;
	
	F.close();
	G.close();
}