#include <fstream>
#include <iostream>
using namespace std;
ifstream in("gfact.in");
ofstream out("gfact.out");
int pas=1<<30,p,q;
int fact[1000000000];
int putere(int,int);
int nr(int,int,int);
int main()
{
    int i=0,d=2,cop,m,fmax=-1;
    in >> p >> q;
    cop=p;
    for(;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;
    while(n>=nr)
    {
        div+=n/nr;
        n/=nr;
        //cout << n << " " << aa << endl;
    }
    return div;
}