#include <stdio.h>
#define maxl 10000
#include <math.h>

long long i,j,k,n,b,t,x,p,q,nr;
long long fact[maxl],put[maxl],puta[maxl];
long long min;

int main()
{
    freopen("zero2.in","r",stdin);
    freopen("zero2.out","w",stdout);
    
    t=10;
    while (t)
    {
          scanf("%lld %lld",&n,&b);
          
		  for (i=1; i<=k; i++)
		  {
			fact[i]=0;
			puta[i]=0;
			put[i]=0;
		  }

		  k=0;
          if (b%2==0) {++k;fact[k]=2;}
          while (b%2==0) {b/=2;put[k]++;}
          while (b>1)
          {
                x=(int)sqrt(b);p=b;
                for (i=3; i<=x; i+=2)
                {
					if (b%i==0) {k++;fact[k]=i;}
					while (b%i==0) {put[k]++;b/=i;}
				}
                if (p==b)
                {
                   fact[++k]=b;
                   put[k]=1;
                   b=1; 
                }
          }

          for (i=1; i<=k; i++)
          {
			  for (p=fact[i]; p<=n; p*=fact[i])
              {
                  x=n/p;
                  nr=x*(n+1)-p*x*(x+1)/2;
                  puta[i]+=nr;
			  }
          }
          
		  min=puta[1]/put[1];
		  for (i=2; i<=k; i++)
          {
              q=puta[i]/put[i];
              if (q<min) min=q;
          }

		  printf("%lld\n",min);

		  --t;
	}

	return 0;
}