#include <bits/stdc++.h>
using namespace std;

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

const int nmax=5000005;
int i,p,q,divizor,put,factmax,nrprim,boss;
int primes[nmax],fr[nmax];

bool descompunere (int numar , int necesar , int ori)
{
    int imp,powsofar,current=1;
    powsofar=0;
    while (powsofar<necesar && current<=numar/ori)
    {
        current*=ori;
        powsofar+=(numar/current);
    }

    if (powsofar>=necesar)
     return 1;
   return 0;
}

int bin_search (int x)
{
    int st,dr,numar,mij,lastp=-1,aux;
    st=0;
    dr=200000;

    while (st<=dr)
    {
        mij=(st+dr)/2;
        numar=mij;
        aux=descompunere(numar,fr[x],primes[x]);
        if (aux)
        {
            lastp=numar;
            dr=mij-1;
        }
        else
           st=mij+1;
    }
    if (lastp>0) return lastp;
    return -1;
}

int main()
{
    f>>p>>q;
    divizor=2;

    while (p!=1)
    {
        put=0;
        while (p%divizor==0)
        {
            p/=divizor;
            put++;
        }
        if (put>0)
        {
            primes[++nrprim]=divizor;
            fr[nrprim]=put*q;
        }
        divizor++;
    }

    for (i=1;i<=nrprim;i++)
    {
        boss=bin_search(i);
        if (boss>factmax)
         factmax=boss;
    }

    g<<factmax;
    return 0;
}