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




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;
    for (;step < 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++) {
    b = 0;
    while (P % i == 0) P /= i, b++;
    TOT = b * q;
    if (b) MAX = max(MAX, caut(i));
  }

TOT=q;

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