#include<bits/stdc++.h>
#define god dimasi5eks
#pragma GCC optimize("O3")
#define fi first
#define se second
#define pb push_back
#define pf push_front
 
#define fisier 1
 
using namespace std;
 
typedef long long ll;
 
const int mod = 1000000007;
const double dancila = 3.14159265359; // PI 
const double eps = 1e-9;
 
 
ll ct(ll n, ll b)
{
	ll ans = 0;
	for(ll i = b; i <= n; i *= b)
	{
		ll k = n / i;
        ans += 1LL * i * k * (k-1) / 2;
        ans += 1LL * (n - k * i + 1) * k;
	}
	return ans;
}
 
int main()
{
	#ifdef fisier
		ifstream cin("zero2.in");
		ofstream cout("zero2.out");
	#endif
	
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	
	int t = 10;
	for(; t; --t)
	{
		ll n, b;
		cin >> n >> b;
		ll ans = (1LL<<60);
		for(int i = 2; i * i <= b; ++i)
			if(b % i == 0)
			{
				int ex = 0;
				while(b%i == 0)
					++ex, b /= i;
				ans = min(ans, ct(n, i)/ex);
			}
		if(b > 1)
			ans = min(ans, ct(n, b));
		cout << ans << '\n';
	}
	return 0;
}