#include <cstdio>
#include <iostream>
#define INF "gfact.in"
#define OUF "gfact.out"
#define NMAX 2048
using namespace std;

inline void fact(int f[],int p[],int &dim,unsigned long long nr)
{
	unsigned long long mem,k,ko;
	int i;
	i=0;k=2;mem=nr;
	while(k*k<=nr)
	{
		if(mem%k==0)
		{
			++i;f[i]=k;
			while(mem%k==0&&mem)
			{
				mem/=k;
				++p[i];
			}
			++i;f[i]=nr/k;ko=nr/k;
			while(mem%ko==0&&mem)
			{
				mem/=ko;
				++p[i];
			}
		}
		++k;
	}
	if(!i) { ++i;f[i]=nr;p[i]=1; }
	dim=i;
}

inline int xpfact(int x,unsigned long long fact)
{
	unsigned long long k;
	int pwr=0;
	k=x;
	while(k<=fact)
	{
		pwr+=fact/k;
		k*=x;
	}
	return pwr;
}

int main()
{
	FILE *in,*out;
	int i,ft[NMAX],pt[NMAX]={0},dim=0;
	unsigned long long st,dr,mij,p,q,b,xp,alfa;
	in=fopen(INF,"r");
	out=fopen(OUF,"w");
	fscanf(in,"%lld%lld",&p,&q);
	fact(ft,pt,dim,p);
	for(i=1;i<=dim;++i) pt[i]*=q;
	b=0;
	for(i=1;i<=dim;++i)
	{
		st=1;dr=ft[i]*pt[i];alfa=dr;
		while(st<=dr)
		{
			mij=(st+dr)/2;
			xp=xpfact(ft[i],mij);
		        if(xp==pt[i]&&mij<alfa) alfa=mij;
			if(xp<pt[i]) st=mij+1;
			else dr=mij-1;
		}
		if(alfa>b) b=alfa;
	}

	fprintf(out,"%lld\n",b);
	fclose(in);fclose(out);
	return 0;
}