#include <fstream>
#include <vector>
#include <algorithm>

using namespace std;

ifstream input("TIMK.inp");
ofstream output("TIMK.out");
int n, m, index = 2, temp;
int res = INT32_MAX;

struct num
{
	int a;
	int count;
};

int lagrange(int n, int m)
{
	int i = 1;
	int res = 0;
	while ((int)(n / pow(m, i)) != 0)
	{
		res += n / pow(m, i);
		++i;
	}
	return res;
}

int main()
{
	input >> n >> m;
	vector <num> a;
	while (m != 1)
	{
		if (m % index == 0)
		{
			if (a.size() == 0 || a.back().a != index)
			{
				a.push_back(num{ index, 1 });
			}
			else if (a.back().a == index)
			{
				a.back().count++;
			}
			m /= index;
		}
		else
		{
			index++;
		}
	}
	for (int i = 0; i < a.size(); ++i)
	{
		temp = lagrange(n, a[i].a) / a[i].count;
		if (temp < res)
		{
			res = temp;
		}
	}
	output << res;
	return 0;
}