#include <stdio.h>

#define maxx 10010
#define maxn 25
#define ll unsigned long long
#define maxv 63

int n,m,k;
int a[maxx],c[maxn],p[maxn];
ll sol;

void diviz(int n)
{
     int i,l=0,aux;k=0;
     
     for (i=1;i*i<=n;i++)
       if (n%i==0) a[++l]=i;
       
     if (a[l]*a[l]==n) aux=l-1;
     else aux=l;
     
     for (i=aux;i>0;i--) a[++l]=n/a[i];
     
     for (i=2;i<=l;i++)
       if (n%a[i]==0)
       {
           c[++k]=a[i];
           p[k]=0;
           while (n%a[i]==0)
           {
                 n/=a[i];
                 p[k]++;
           }
       }
}

int main()
{
    freopen("zero2.in","r",stdin);
    freopen("zero2.out","w",stdout);
    
    int T,i;
    ll x,rez,y;
    
    T=10;
    
    while (T>0)
    {         
          scanf("%d %d",&n,&m);
          diviz(m);
          sol=0LL+1<<maxv;
                    
          for (i=1;i<=k;i++)
          {
              x=c[i];
              rez=0;
              while (x<=n)
              {
                    y=n/x;
                    rez+=y*y+(n%x)*y;
                    x*=c[i];
              }
              
              if (rez/p[i]<sol) sol=rez/p[i];
          }
          printf("%lld\n",sol);
          T--;     
    }
    
    return 0;
}