#include <bits/stdc++.h>

using namespace std;
ifstream f1("TIMK.INP");
    ofstream f2("TIMK.OUT");
int f[10000000];
bool ex = false;
int lagrange(int n, int p)
{
	int i = 1;
	int res = 0;
	while ((int)(n / pow(p, i)) != 0)
	{
		res += n / pow(p, i);
		++i;
	}
	return res;
}

int main()
{int n,i=2,min=2e9,m,j;
f1>>n>>m;
while (m>1)
{ if (m%i==0)
 {
     f[i]++;
     m=m/i;
 }
 else if (i*i<=m) i++;
 else {f[m]++; break;}
}
for (i=2;i<=n;i++)
{  j=n/i;
if (f[i]>0)
  {if (min>lagrange(n,i)/f[i]) min=lagrange(n,i)/f[i];
  ex = true;
  if (min!=2e9) min=0;}
  }
  if (ex)
f2<<min;
else
f2 << 0;
}
