#include<bits/stdc++.h>
using namespace std;
ifstream fi("TIMK.inp");
ofstream fo("TIMK.out");
int main(){
int n,k,t,c=INT_MAX,tg=0,ans,i=2;
fi>>n>>k;
t=k;
while(t!=1){
    while(t%i==0){ tg++; t=t/i; }
    if(tg!=0 && tg<=c){ ans=i; c=tg; }
    ++i;tg=0;
}
tg=1;
for(int i=0;i<c;++i)tg=tg*ans;

c=0;
while(n/tg!=0){
        c+=n/tg;
        tg=tg*ans;
}
fo<<c;
}
