#include <cstdio>
#define FIN "gfact.in"
#define FOUT "gfact.out"
#define Q 30000
int p,q;
long long b,v[Q][2],max;
void read()
{
	freopen(FIN, "r",stdin);
	scanf("%d%d", &p, &q);
}
int calc(int x,int y)
{
	int i=0;
	v[0][0]=1;
	v[0][1]=0;
	while (v[i][1]<=y)
	{
		++i;
		v[i][0]=v[i-1][0]*x;
		v[i][1]=x*v[i-1][1]+1;
	}
	return i;
}
void solve(int x,int y)
{
	int i,r=y;
	i=calc(x,y);
	b=0;
	while (r)
	{
		while (v[i][1]>r)
			--i;
		b+=(r/v[i][1])*v[i][0];
		r%=v[i][1];
	}
}
void comp()
{
	int i=1,j;
	for(i=2 ; i*i<=p ; ++i)
	{
		j=0;
		if (p%i==0)
		{
			while (p%i==0)
			{
				++j;
				p/=i;
			}
			solve(i,j*q);
			if(b>max)
				max=b;
		}
	}
	if(p!=1)
	{
		solve(p,q);
		if(b>max)
			max=b;
	}
}
void write()
{
	freopen(FOUT,"w",stdout);
	printf("%lld\n", max);
}
int main()
{
	read();
	comp();
	write();
}