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

inline int prim(long long nr2)
{
	long long  div;
	int ok;
	ok=1;div=2;
	while(div*div<=nr2&&ok)
	{
		if(nr2%div==0) ok=0;
		++div;
	}
	return ok;
}

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

inline int xpfact(int x,long long fact)
{
	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;
	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;
//		cout<<ft[i]<<' '<<pt[i]<<endl;
		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;
}