#include <iostream>
#include <fstream>
using namespace std;
ifstream f("gfact.in");
ofstream g("gfact.out");
int fact[200],exp[200],n,q;
long long p,i,r=0,step=1LL<<60;
long long zero(long long n,long long m)
{
    long long nr=0;
    while(n>=m)
        nr+=(n/=m);
    return nr;
}
bool check(long long nr)
{
    for(int j=0;j<n;j++)
        if(zero(nr,fact[j])<exp[j]*q)
            return 0;
    return 1;
}
int main()
{
    f>>p>>q;
    if(p%2==0)
    {
        fact[0]=2;
        while(p%2==0)
        {
            p/=2;
            exp[0]++;
        }
        n=1;
    }
    if(p%3==0)
    {
        fact[n]=3;
        while(p%3==0)
        {
            p/=3;
            exp[n]++;
        }
        n++;
    }
    for(i=5;p>1&&i*i<=p;i+=6)
    {
        if(p%i==0)
        {
            fact[n]=i;
            while(p%i==0)
            {
                p/=i;
                exp[n]++;
            }
            n++;
        }
        if(p%(i+2)==0)
        {
            fact[n]=i+2;
            while(p%(i+2)==0)
            {
                p/=i+2;
                exp[n]++;
            }
            n++;
        }
    }
    if(p>1)
    {
        fact[n]=p;
        exp[n]=1;
        n++;
    }
    for (i=0;step;step>>=1)
    {
        if(!check(i+step))
            i+=step;
    }
    g<<i+1;
    return 0;
}