#include <stdio.h>

#define MAX_FACT 128

typedef long long llong;

int N, B, fact[MAX_FACT], putere[MAX_FACT];

llong baga(int P)
{
    int k, aux = P;
    llong r = 0;

    while(N / P)
    {
        k = N/P;
        r += (llong)P*(k-1)*k/2+(llong)(N-k*P+1)*k;
        if( (llong)P*aux > (llong)N )
            break ;
        P = P*aux;
    }

    return r;
}

void read_and_solve(void)
{
    int i, T = 0;
    llong res, aux;

    scanf("%d %d\n", &N, &B);

    if(B % 2 == 0)
    {
        fact[++T] = 2, putere[T] = 0;
        while(B % 2 == 0)
            putere[T]++, B /= 2;
    }
    for(i = 3; i*i <= B; i+=2)
     if(B%i == 0)
     {
        fact[++T] = i, putere[T] = 0;
        while(B%i == 0)
            putere[T]++, B /= i;
     }
    if(B != 1)
        fact[++T] = B, putere[T] = 1;

    res = baga(fact[1]) / putere[1];
    for(i = 2; i <= T; i++)
    {
        aux = baga(fact[i]) / putere[i];
        if(aux < res)
            res = aux;
    }

    printf("%lld\n", res);
}

int main(void)
{
    freopen("zero2.in", "rt", stdin);
    freopen("zero2.out", "wt", stdout);

    int teste = 10;

    while(teste--)
        read_and_solve();

    return 0;
}