#include<iostream>
#include<cmath>
#define ll long long 
using namespace std;
ll n,k,ans=1e18;
bool sushu(ll x){
	if(x==1)return 0;
    if(x==2||x==3)
        return 1;
    if(x%6!=1&&x%6!=5)
        return 0;
    for(ll i=5;i*i<=x;i+=6)
        if(x%i==0||x%(i+2)==0)return 0;
    return 1;
}
int main(){
	cin>>n>>k;
	for(ll i=1;i*i<=k;i++){
		if(sushu(k)){
			ans=0;
			for(ll j=k;j<=n;j*=k)ans+=(n/j);
			break;
		}
		if(i==1)continue;
		if(k%i==0){
			ll p,e,g,l;
			if(sushu(i)){
				p=i,e=0,g=0,l=k;
				while(l%p==0){
					e++;
					l/=p;
				}
				if(e){
					for(ll j=p;j<=n;j*=p)g+=(n/j);
					ans=min(ans,(g/e));
				}
			}
			if(sushu(k/i)){
				p=k/i,e=0,g=0,l=k;
				while(l%p==0){
					e++;
					l/=p;
				}
				if(e){
					for(ll j=p;j<=n;j*=p)g+=(n/j);
					ans=min(ans,(g/e));
				}
			}
		}
	}
	cout<<ans;
	return 0;
}