题目链接：http://codeforces.com/contest/1114/problem/C

#include<cstdio>
#include<map>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<vector>
using namespace std;
typedef long long ll;
const int N=1e6+5;
bool p[N];
int prime[N],cnt=0;
void isprime(){
	p[0]=p[1]=true;
	for(int i=2;i<N;i++){
		if(!p[i]) prime[cnt++]=i;
		for(int j=0;j<cnt&&(ll)i*prime[j]<N;j++){
			p[i*prime[j]]=true;
			if(i%prime[j]==0) break;
		}
	}
}
map<ll,int> mp;
vector<ll> v;
int main(){
	isprime();
	ll n,b;
	scanf("%I64d%I64d",&n,&b);
	for(int i=0;i<cnt&&b!=1;i++){      //将b唯一分解
		int res=0;
		while(b%prime[i]==0){
			res++;
			b/=prime[i];
		}
		if(res) {
			mp[prime[i]]=res;
			v.push_back(prime[i]);
		}
	}
	if(b!=1) {
		mp[b]=1;
		v.push_back(b);
	}
	ll ans=999999999999999999;
	for(int i=0;i<v.size();i++){        //n！里有多少组b的因子就有多少尾0
	    ll a=n;
		ll t=0;
		while(a>=v[i]){
			t+=a/v[i];
			a/=v[i];
		} 
		ans=min(ans,t/mp[v[i]]);
	}
	printf("%I64d\n",ans);
	return 0;
}