#include <fstream>

using namespace std;
ifstream fi("timk.inp");
ofstream fo("timk.out");
int larg(int p,int n)
{
	int o=p;
	int u=0;
	while(o<=n)
	{
		u+=n/o;
		o*=p;
	}
	return u;
}
int main()
{
    ios::sync_with_stdio(false);
    int n,m;
    fi >> n >> m;
    int tt,j = 2,mx = 2e9,d = 0,tg = m;
    while (tg != 1)
    {
        d = 0;
        while (tg%j == 0)
        {
            tg /= j;
            ++d;
        }
        long long t = 0,tt = j;
        while (d > 0 && n/tt != 0)
        {
           t += n/tt;
           tt *= tt;
        }
        if (d > 0 && t/d < mx) mx = t;
        if (tg == 1) break;
        if (j == 2) ++j;
        else j += 2;
    }
    fo << mx;
    return 0;
}

