#include <cstdio>
#include <cstring>

#define file_in "zero2.in"
#define file_out "zero2.out"

#define Nmax 600100

int n,i,N,B,d,e,v[Nmax],suma,min,nrp,nrf,j,max,put,t;

int main()
{
	freopen(file_in,"r",stdin);
	freopen(file_out,"w",stdout);
	
		 
	for (t=1;t<=10;++t)
    {
	
		scanf("%d %d", &N, &B);

		//descompune B
		
		d=2;
		e=0;
		while(B%d==0)
		{
			e++;
			B/=d;
		}
		if (e>0)
		{
			max=d;
			v[d]=e;
		}
		
		d=3;
		while(d*d>=B)
		{
			 e=0;
		     while(B%d==0)
		     {
			    e++;
			    B/=d;
		     }
		     if (e>0)
		     {
			   max=d;
			   v[d]=e;
		     }
		d+=2;
		}
		
		if (B>1) v[B]=1;
		min=0x3f3f3f3f;
		
		for (i=2;i<=max;++i)
		if (v[i]>0)
		{
			put=i;
			suma=0;
			
			for (j=2;j<=N;++j) 
            { 
               nrf=0; 
               n=j; 
               d=put; 
               while(n>=d) 
               { 
                nrf+=n/d; 
                n/=d; 
               } 
               if (nrf!=0)    
				 suma+=nrf;
            } 
			if ((suma/v[i])<min)
				min=(suma/v[i]);
		}
		
		printf("%d\n", min);
	}
	
	fclose(stdin);
	fclose(stdout);
	
	return 0;
	
}