#include <stdio.h>

typedef long long lint;

lint n,b,sol;

lint doit(lint x,lint p)
{
    lint c,r;
    c=x/p-1; r=x%p;
    return c*(c+1)/2*p+(c+1)*(r+1);
}

lint count(lint x,lint p)
{
    lint j,aux=0;
    for(j=p;j<=x;j*=p)
        aux+=doit(x,j);
    return aux;
}

int main()
{
    lint i,j,x;
    freopen("zero2.in","r",stdin);
    freopen("zero2.out","w",stdout);
    while(scanf("%lld %lld",&n,&b)==2)
    {
        sol=0;
        for(i=0;i<63;++i)
            sol|=1ll<<i;
        for(i=2;i*i<=b;++i)
        {
            for(j=0;b%i==0;b/=i,++j);
            if(!j)
                continue;
            x=count(n,i);
            if(x/j<sol)
                sol=x/j;
        }
        if(b!=1)
        {
            x=count(n,b);
            if(x<sol)
                sol=x;
        }
        printf("%lld\n",sol);
    }
    return 0;
}