#include<fstream>
using namespace std;
long long n, b, aux, i, sol, nr, xdiv, cat;
struct cub {
    long long div;
    long long nr;
    long long  c;
};
cub x[100003];
ifstream in("zero2.in");
ofstream out("zero2.out");
int main(){
    aux=10;
    for(;aux--;){
        sol=40000000000001;
        for(i=1; i<=nr; i++){
            x[i].div=0;
            x[i].nr=0;
            x[i].c=0;
        }
        nr=0;
        in>>n>>b;
        for(i=2; i*i<=b; i++){
            if(b%i==0){
                x[++nr].div=i;
                while(b%i==0){
                    x[nr].nr++;
                    b/=i;
                }
            }
        }
        if(b!=1){
            x[++nr].div=b;
            x[nr].nr=1;
        }
        for(i=1; i<=nr; i++){
            xdiv=x[i].div;
            while(n/xdiv>0){
                x[i].c+=xdiv*((n/xdiv)*(n/xdiv+1)/2);
                    x[i].c-=(xdiv-1-n%xdiv)*(n/xdiv);
                xdiv*=x[i].div;
            }
        }
        for(i=1; i<=nr; i++)
            if(x[i].c/x[i].nr<sol)
                sol=x[i].c/x[i].nr;
        out<<sol<<"\n";
    }
return 0;
}