#include <stdio.h>
#define PMAX 34000
#define MIN(a,b) (((a)<(b))?(a):(b))

int P[PMAX], V[PMAX], N, B, F[PMAX], E[PMAX], Case;

int main()
{
        int i, j, np=0, nf=0;
        long long k, p, nzero=-1, nz=0;

        for (i = 2; i < PMAX; i++)
            if (!V[i])
            {
                P[np++] = i;
                for (j = i; j < PMAX; j+=i) V[j] = 1;
            }

        freopen("zero2.in", "r", stdin);
        freopen("zero2.out", "w", stdout);

        for (Case=10; Case; Case--)
        {
                scanf("%d%d", &N, &B);

                for (i=0; ((B>1)&&(i<np)); i++)
                {
                    while ((B>1)&&(!(B%P[i]))) F[nf] = P[i], E[nf]++, B /= P[i];
                    if (E[nf]) nf++;
                }
                if (B>1) F[nf] = B, E[nf++] = 1;

                for (i = 0; i < nf; i++)
                {
                    for (nz = 0, p = F[i]; p <= N; p*=F[i])
                    {
                        k = (N/p) - 1;
                        nz = nz+p*k*(k+1)/2+(k+1)*(N-p*(k+1)+1);
                    }
                    if (nzero<0) nzero = nz;
                    nzero = MIN(nzero, nz/E[i]);
                }

                printf("%lld\n", nzero);
                    
                for (i = 0; i < nf; i++) F[i] = E[i] = 0;
                nf = 0; nzero = -1;
        }
        
        return 0;
        
}