#include <iostream>
#include <fstream>
using namespace std;
int a[100001],b[100001],k,p,q;

void desc()
{

int i=2;
while(i*i<=p)
{
if(p%i==0)
{
    k++;
    a[k]=i;
    while(p%i==0)
        {
            b[k]++;
            p/=i;
        }
}
i++;
}
if(p!=1)
    {
    k++;
    a[k]=p;
    b[k]=1;
    }
}

int zero(int n,int div)
{
int nr=0;
while(n>=div)
{
nr+=n/div;
n/=div;
}
return nr;
}

int OK(int x)
{
for(int i=1;i<=k;i++)
if(zero(x,b[i])<(b[i]*q))
return 0;
return 1;
}

int cb()
{
int i=0;
int pas=1<<30;
while(pas!=0)
{
if(OK(i+pas)==0)
    i+=pas;
    pas/=2;
}
return i+1;
}


int main()
{
    ifstream f("gfact.in");
    ofstream g("gfact.out");
    int p,q;
    cout<<"ok";
    f>>p>>q;
    desc();
    cout<<k;
    g<<cb();

    return 0;
}