#include <fstream>
#include <iostream>
using namespace std;
ifstream in("gfact.in");
ofstream out("gfact.out");
int pas=1<<30,p,q;
int fact[100000000];
int putere(int,int);
int nr(int,int,int);
int main()
{
    int i=0,cop,m,fmax=-1;
    in >> p >> q;
    cop=p;
    for(register int d=2; d*d<=cop; ++d)
        while(cop%d==0)
        {
            cop/=d;
            fact[d]++;
            m=d;
        }
    if(cop>1)
    {
        fact[cop]++;
        m=cop;
    }
    for(i=2; i<=m; ++i)
    {
        int j=0;
        if(fact[i])
            while(pas)
            {

                if(nr(j+pas,i,fact[i])<=q)
                    j+=pas;
                pas/=2;
            }
        if(j>fmax) fmax=j;
    }
    out << fmax;
    return 0;
}
int nr(int n,int nr,int put)
{
    int div=0,copie;
    while(put)
    {
        copie=n;
        while(copie>=nr)
        {
            div+=copie/nr;
            copie/=nr;
        }
        --put;
    }
    return div;
}