#include<stdio.h>
FILE*f=fopen("zero2.in","r");
FILE*g=fopen("zero2.out","w");
long long Nr(long long N,long long p) //puterea la care apare p in descompunerea lui N!
  {
  long long x,i,nr=0,P;
  for(i=2;i<=N;++i)
  
    {
    x=i;
    P=p;
    while(x/P!=0)
     {
     nr+=(x/P);
     P*=p;
     }
   }
  return nr;
  }
long long fact(long long B,long long N) //factorizez numarul B
  {
  long long i,r, nr, min=100000000;
  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(int N, int 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;
 }