#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll n,d,m;
void r(ll &x)
{
    x=0;
    char a;
    a=getchar();
    for (;a<'0'||a>'9';a=getchar());
    for (;a>='0'&&a<='9';a=getchar())
        x=x*10+a-'0';
}
void w(ll x)
{
    if (x>9) w(x/10);
    putchar(x%10+'0');
}
vector <long long> b,a;
ll mu(ll a,ll n)
{
    ll k;
    if (n==1) return a;
    k=mu(a,n/2);
    if (n%2==0) return k*k;
    else return k*k*a;
}
ll Solve(ll a,ll n)
{
    ll i=1;ll d=0;
    ll k=mu(a,i);
    while (k<=n)
    {
        d=d+n/k;
        i++;
        k=mu(a,i);
    }
    return d;
}
int main()
{
    freopen("TIMK.inp","r",stdin);
    freopen("TIMK.out","w",stdout);
    ios_base::sync_with_stdio(false);
    r(n);r(m);
    //cin>>n>>m;
    long long i=2;
    long long k=m;
    while (i<=k)
    {
        while (k%i==0){
            k=k/i;
            b.push_back(i);
        }
        i++;
    }
    //cout<<Solve(5,124);
    long long gtnn=INT_MAX;
    sort(b.begin(),b.end());
    a.push_back(b[0]);
    for (int i=1;i<b.size();i++)
    {
        if (b[i]!=b[i-1])
        {
            a.push_back(b[i]);
        }
    }
    k=0;
    for (int i=0;i<a.size();i++)
    {
        k=Solve(a[i],n);
        gtnn=min(gtnn,k);
    }
    w(gtnn);

}

