using namespace std;

#include <cstdio>
#include <vector>

#define FIN "zero.in"
#define FOUT "zero.out"

int N, B;
long long ans;
vector <pair <int, int> > D;

long long slbz(int N, int t)
{
	// 1/t + 2/t + ... + N/t
	return (long long)((N+1)/t)*((N+1)/t-1)/2*t+((N+1)%t)*(N/t);
}

long long calc(int x)
{
	long long res = 0, t;
	for (t = x; t <= N; t *= x)
		res += slbz(N, t);
	return res;
}

int main()
{
	int i, _B, _P;
	freopen("zero2.in", "r", stdin);
	freopen("zero2.out", "w", stdout);
	vector <pair <int, int > > :: iterator it;
	for (int tests = 10; tests--; ) {
		scanf("%d %d", &N, &B);
	
		for (i = 2, _B = B; i*i <= _B; ++i)
			if (_B%i == 0) {
				for (_P = 0; _B%i == 0; _B /= i)
					++_P;
				D.push_back(make_pair(i, _P));
			}
		if (_B > 1)
			D.push_back(make_pair(_B, 1));
		
		for (ans = (long long)1e+40, it = D.begin(); it != D.end(); ++it) {
			ans <?= calc(it->first)/it->second;
		}
		printf("%lld\n", ans);
		
		D.clear();
	}
	return 0;
}