#include <stdio.h>
#include <math.h>
#include <algorithm>

using namespace std;

int b;
long long n;

int main()
{
	freopen("zero2.in","r",stdin);
	freopen("zero2.out","w",stdout);
	for (int t = 10; t; t--)
	{
		scanf("%lld %d", &n, &b);
		int bi = b;
		long long minim = (long long) LONG_MAX * LONG_MAX;
		for (int i = 2; i <= sqrt((double) bi) && b > 1; i++)
			if (!(b % i))
			{
				long long nrdv = 0;
				while (!(b % i))
				{
					b /= i;
					nrdv++;
				}
				long long x = i, nr = 0;
				while (x <= n)
				{
					long long r = n / x;
					nr += (((r + 1) * r / 2 * x) - ((r + 1) * x - 1 - n) * r);
					x *= i;
				}
				minim = min(minim, nr / nrdv);
			}
		if (b > 1)
		{
			long long x = b, nr = 0;
			while (x <= n)
			{
				long long r = n / x;
				nr += (((r + 1) * r / 2 * x) - ((r + 1) * x - 1 - n) * r);
				x *= b;
			}
			minim = min(minim, nr);
		}
		printf("%lld\n", minim);
	}
	fclose(stdin);
	fclose(stdout);
	return 0;
}