#include <stdio.h>
#define minim(a, b) ((a < b) ? a : b)
#define ll long long

int N, B, rad, e[32], p[32];

int main(void)
{
    int T = 10, i, d = 0, nr = 0, E, c, r;
    ll cnt = 0, x = 0;
    
    freopen("zero2.in", "r", stdin);
    freopen("zero2.out", "w", stdout);    
    
    for (; T; T--)
    {
        scanf("%d %d", &N, &B);
                
        for (rad = 1; rad * rad <= B; rad++); rad--;
                
        nr = 0; d = 1;
        while (B > 1 && d < rad)
        {
              d++;
              
              if (B % d == 0)
              {  
                 p[++nr] = 0; e[nr] = d;  
                 while (B % d == 0)
                       p[nr]++, B /= d;
              }        
        }
        if (B > 1) e[++nr] = B, p[nr] = 1, B = 1;
                
        cnt = 2000000005;
        for (i = 1; i <= nr; i++)
        {
            E = 1; x = 0;
            while ((ll)E * e[i] <= (ll)N)
            {
                  E *= e[i];
                  c = (N+1) / E; r = (N+1) % E;
                     
                  x += (ll)E * (c-1) * c / 2 + (ll)c * r;
            }
            
            cnt = minim(cnt, x / p[i]);
        }
        
        printf("%lld\n", cnt);
    }
    
    return 0;
}