#include<stdio.h>
FILE*f=fopen("zero2.in","r");
FILE*g=fopen("zero2.out","w");
long long unsigned S(long long unsigned N, long unsigned p)
  {
  long long unsigned k;
  k=(N/p)-1;
  return k*(k+1)/2*p+(k+1)*(N-(k+1)*p+1);
  }
long long unsigned Nr(long long unsigned N,long long unsigned p) //puterea la care apare p in descompunerea lui N!
  {
  long long unsigned x,i,nr=0,P;
  P=p;
  while(N/P!=0)
    {
    nr+=S(N,P);
    P*=p;
    }

  return nr;
  }
long long unsigned fact(long long B,long long N) //factorizez numarul B
  {
  long long unsigned i,r, nr, min;
  min=(1<<20);
  min*=(1<<20);
  min*=(1<<23);
  
  if(B%2==0)
    {
    r=0;
    while(B%2==0) {++r; B/=2;}
    nr=Nr(N,2)/r;
    if(nr<min) min=nr;
    }
  for(i=3;i*i<=B;i+=2)
    {
    for(r=0;B%i==0;++r,B/=i);
    if(r)
      {
      nr=Nr(N,i)/r;
      if(nr<min) min=nr;
      }
    }
  if(B>1)
    {
    nr=Nr(N,B);
    if(nr<min) min=nr;
    }
  return min;
  }
void solve(long long N, long long B)
  {
  long long sol;
  sol=fact(B,N);
  fprintf(g,"%lld\n",sol);
  }
int main()
 {
 long long n,b,t=10;
 while(t--)
  {
  fscanf(f,"%lld %lld",&n,&b);
  solve(n,b);
  }
 return 0;
 }