#include <bits/stdc++.h>

using namespace std;

ifstream f("zero2.in");
ofstream g("zero2.out");

int count0(int n,int p)
{
    function<int(int,int)> S=[](int n,int p)
    {
        int k=n/p-1;
        return k*(k+1)/2*p+(k+1)*(n-(k+1)*p+1);
    };
    int p1=p,s=S(n,p),result=0;
    while(s>0)
    {
        result+=s;
        p1*=p;
        s=S(n,p1);
    }
    return result;
}

vector<pair<int,int>> FP(int n)
{
    vector<pair<int,int>> result;
    int k=0;
    while(n%2==0) k++,n/=2;
    if(k!=0) result.push_back({2,k});
    int p=3;
    while(n>1)
    {
        int k=0;
        while(n%p==0) k++,n/=p;
        if(k!=0) result.push_back({p,k});
        p+=2;
    }
    return result;
}

int main()
{
    int Q=10;
    for(int n,p;Q--;)
    {
        f>>n>>p;
        vector<pair<int,int>> V=FP(p);
        int r=INT_MAX;
        for(auto i:V)
            r=min(r,count0(n,i.first)/i.second);
        g<<r<<'\n';
    }
    return 0;
}