vector <pair <int, int> > p;

int main() {
	freopen("input.txt", "r", stdin);
	freopen("output.txt", "w", stdout);
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int n, m;
	cin >> n >> m;
	int x = m;
	for (int i = 2; x > 1; i++) {
		if (x % i == 0) {
			int cnt = 0;
			while (x % i == 0) {
				cnt++;
				x /= i;
			}
			p.push_back({ i, cnt });
		}
	 }
	long long ans = 10000000000;
	for (int i = 0; i < p.size(); i++) {
		long long cnt = 0;
		int x = n;
		while (x > 0) {
			x /= p[i].first;
			cnt += x;
		}
		ans = min(ans, cnt / p[i].second);
	}
	cout << ans;
	return 0;
}