Wa on 16，95分。

#include<bits/stdc++.h>
using namespace std;
#define LL long long
#define gc getchar
#define pc putchar
#define pb push_back
#define ls u<<1
#define rs u<<1|1
#define mp(i,j) make_pair(i,j)
const int ri=1e6+5;
template<typename T>inline void read(T&x){x=0;int f=1;char ch=gc();while(!isdigit(ch)){if(ch=='-') f=-1;ch=gc();}while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+ch-'0';ch=gc();}x*=f;}
template<typename T,typename ...T1>inline void read(T&x,T1&...x1){read(x);read(x1...);}
LL n,k,minn=LONG_LONG_MAX;
vector<pair<LL,LL>> p;
int main(){
	read(n,k);
    LL ui=k;
    for(LL i=2,cnt=0;i*i<=k;i++){
    	while(k%i==0){
    		cnt++;
    		k/=i;
		}
		if(cnt) p.pb(mp(i,cnt));	
	}
	if(k!=1){
		p.pb(mp(k,1));
	}
	for(auto [x,y]:p){
		LL t=n,cnt=0;
		while(t){
			cnt+=t/x;
			t/=x;
		}
        //cout<<x<<" "<<y<<" "<<cnt<<endl;
		minn=min(minn,cnt/y);
	}
	cout<<minn<<'\n';
	return 0;
}