#include <stdio.h>
#include <string.h>
#define input "zero2.in"
#define output "zero2.out"
long long cati,divizor,p[1000],d[1000],t,n,b,solutie,i,a,putere,cnt;
long long minim(long long a, long long b)
{
	if (a>b) return b;
	return a;
}
void desc(long nr)
{
	cati=0;
	memset(p,0,sizeof(p));
	while (nr%2==0)
		{
		 p[1]++;
		 d[1]=2;
		 cati=1;
		 nr/=2;
		}
	divizor=3;
	while (nr!=1)
		{
		 if (nr%divizor==0)
			{
			 cati++;
			 d[cati]=divizor;
		     while (nr%divizor==0)
				{
				 p[cati]++;
				 nr/=divizor;
				}
			}
		 divizor+=2;
		 if (divizor*divizor>=nr&&nr!=1)
			{
			 cati++;
			 d[cati]=nr;
			 p[cati]=1;
			 nr=1;
			}
		}
}
void calcul()
{
	solutie=2000000000;
	i=i;
	for (i=1;i<=cati;i++)
		{
		 a=1; putere=0;
		 cnt=0;
		 while (a*d[i]<=n)
			{
			 a*=d[i];
			 cnt++;
			 putere+=(n-a+1)*cnt;
			}
		 if ((int)(putere/p[i])<solutie) 
			 solutie=(int)(putere/p[i]);
		}
}
int main()
{
	FILE *fin,*fout;
	fin=fopen(input,"r");
	fout=fopen(output,"w");
	t=10;
	while (t--)
		{
		 fscanf(fin,"%lld %lld",&n,&b);
		 desc(b);
		 calcul();
		 fprintf(fout,"%lld\n",solutie);
		}
	fclose(fin);
	fclose(fout);
	return 0;
}