#include <fstream>


#define LE 6000000000000
#define  ll unsigned long long
using namespace std;
ifstream f("gfact.in");
ofstream g("gfact.out");
ll  TOT, p, q, P, MAX, i, b,DE;

ll MEX(ll x ,ll y)
{
    if (x>y) return x ; else return y;
}


ll  bad(ll  val, ll DZ) {
  ll REZ = 0;

  for (;val>=DZ;DZ *= DZ)
  REZ += val / DZ;

  if (REZ >= TOT) return 1;
  return 0;
}


ll caut(ll DIV) {

  ll step = 1, t = 0;
    while ((ll)step<(ll)LE)
    step*=2;

  for (;step;step /= 2)
  if (bad(t + step, DIV) == 0)
      t += step;
  return t + 1;
}



int main() {


  f >> p >> q;P = p;

  for (i = 2;i*i <= p;i++) if (P%i==0) {
    b = 0;
    while (P % i == 0) P /= i, b++;
    TOT = (ll)b * (ll)q;
    if (b) MAX = MEX(MAX, caut(i));
  }

TOT=q;

if(P>1) MAX=MEX(MAX,caut(P));
g<<MAX<<'\n';
  f.close();
  g.close();
  return 0;
}