#include <bits/stdc++.h>

using namespace std;
long long raspuns;
long long divid(long long a,long long b)
{
    long long sum=0,i;
    for(int i=a; i<=b; i*=a) sum+=b/i;
    return sum;
}
void numar(long long  n, long long p)
{
    long long st,dr,mijloc,x;
    if(p==0) return;
    st=0;
    dr=2000000000;
    while(dr-st>1)
    {
        mijloc=st+(dr-st)/2;
        x=divid(n,mijloc);
        if(x>p) dr=mijloc;
        else st=mijloc;
    }
    raspuns=max(raspuns,st-st%n);
}
int main()
{
     long long  p,q,x,put;


    freopen("gfact.in", "r", stdin);
    freopen("gfact.out", "w", stdout);

    scanf("%lld%lld",&p,&q);
    put=0;
    while(p%2==0)
    {
        p=p/2;
        put++;

    }
    put*=q;
    numar(2,put);
    x=3;
    while (p>1)
    {
        put=0;
        while(p%x==0)
        {
            p=p/x;
            put++;
        }
        put*=q;
        numar(x,put);
        x+=2;
    }
    printf("%lld",raspuns);
    return 0;
}