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

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

long long int i,p,q,divizor,put,factmax,nrprim,boss,added;

bool prim()
{
    long long int h;
    for (h=2;h*h<=p;h++)
     if (p%h==0)
      return 0;
    return 1;
}

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

    return powsofar;
}

long long int bin_search (long long int frx , long long int x)
{
    long long int st,dr,numar,mij,lastp=-1,aux;
    st=0;
    dr=(1<<30);
    dr*=dr;

    while (st<=dr)
    {
        mij=(st+dr)/2;
        numar=mij;
        aux=descompunere(numar,frx,x);
        if (aux>=frx)
        {
            dr=mij-1;
        }
        else
           st=mij+1;
    }
    mij=(st+dr)/2;
    numar=mij;
    aux=descompunere(numar,frx,x);
    if (aux<frx)
        mij++;
    return mij;
}

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

    if (p==1)
    {
        g<<1;
        return 0;
    }

    if (prim())
    {
        boss=bin_search(q,p);
        if (boss>factmax)
             factmax=boss;
        added=1;
    }

    long long int ey;
    ey=p;

    while (p>1 && added==0 && divizor*divizor<=ey)
    {
        put=0;
        while (p%divizor==0)
        {
            p/=divizor;
            put++;
        }
        if (put>0)
        {
            boss=bin_search(put*q,divizor);
            if (boss>factmax)
             factmax=boss;
        }
         divizor++;
    }

    g<<factmax;
    return 0;
}