#include<cstdio>
int n,b,i,j,d[100050],p[100050],pt[100050],v[100050],m,nr,k,x,nrr;
long long a,nmin;
FILE *f,*g;
int main(){
    f=fopen("zero2.in","r");
    g=fopen("zero2.out","w");
    for(k=1;k<=10;k++){
        fscanf(f,"%d%d",&n,&b);
        for(i=1;i<=nr;i++){
            d[i]=p[i]=pt[i]=v[i]=0;
        }
        nr=0;
        a=b;
        nmin=1LL<<62;
        for(i=2;i<=b/i;i++){
            if(a%i==0){
                d[++nr]=i;
                a/=i;
                p[nr]=1;
                while(a%i==0){
                    p[nr]++;
                    a/=i;
                }
            }
        }
        if(a!=1){
            d[++nr]=a;
            p[nr]=1;
        }
        for(i=2;i<=n;i++){
            for(j=1;j<=nr&&d[j]<=i;j++){
                m=0;
                x=i;
                while(x%d[j]==0){
                    x/=d[j];
                    m++;
                }
                pt[j]+=v[j]+m;
                v[j]+=m;
            }
        }
        for(i=1;i<=nr;i++){
            if(pt[i]<nmin)
                nmin=pt[i];
        }
        fprintf(g,"%lld\n",nmin);
    }








    fclose(f);
    fclose(g);
    return 0;
}