#include <iostream>
#include <fstream>
using namespace std;
ifstream f ("gfact.in");
ofstream g ("gfact.out");
long long fa[55555],pu[55555];
long long legendre(long long fact,long long mijl)
{
    long long ct,x;
    ct=0;
    x=fact;
    while (x<=mijl)
    {
        ct=ct+mijl/x;
        x=x*fact;
    }
    return ct;
}
int main()
{
    long long p,q,d,put,n,maxx,st,dr,mijl,b,i;
    f>>p>>q;
    d=2;
    n=0;
    while (d*d<=p)
    {
        put=0;
        while (p%d==0)
        {
            put++;
            p=p/d;
        }
        if (p!=0)
        {
            n++;
            fa[n]=d;
            pu[n]=put;
        }
        d++;
    }
    if (p!=1)
    {
        n++;
        fa[n]=p;
        pu[n]=1;
    }
    maxx=0;
    for (i=1; i<=n; i++)
    {
        st=1;
        dr=2000000000;
        while (st<=dr)
        {
            mijl=(st+dr)/2;
            if (legendre(fa[i],mijl)<pu[i]*q)
                st=mijl+1;
            else
            {
                dr=mijl-1;
                b=mijl;
            }
        }
        if (b>maxx)
            maxx=b;
    }
    g<<maxx;
    return 0;
}