#include <fstream>
#include<cmath>
using namespace std;

ifstream f("gfact.in");
ofstream g("gfact.out");

const int ND = 50;
int d[ND], e[ND], nd, q;
long long putere (long long x, long long p){
    long long s=0;
    while(x!=0){
        s=s+x/p;
        x=x/p;
    }
    return s;
}

void desc(long long p)
{
    long long i;
    for(i=2 ; i*i<=p ; i++)
    {
        if(p%i==0)
        {
            d[++nd] = i;
            while(p%i==0)
            {
                e[nd]++;
                p /= i;
            }
        }
    }
    if(p!=1)
    {
        d[++nd] = p;
        e[nd] = 1;
    }
}

bool divide(int x)
{
    for(int i=1 ; i<=nd ; i++)
        if(putere(x,d[i])<e[i]*q)
            return false;
    return true;
}
int main()
{
    long long p,pas=1<<30,i,j;
    f>>p>>q;
    desc(p);
    i=0;
    while(pas!=0){
        if(divide(i+pas)==false)
            i+=pas;
        pas/=2;
    }
    g<<i+1;
    return 0;
}