Program gfact;
type tip=record
     fact,put:longint;
     end;
 var p:array [1..100] of tip;
    n,a,q,max,b,i:longint;
    fi,fo:text;
procedure descompune();
  var j,k,s:longint;
 begin
 i:=2; k:=0;
  while i<=trunc(sqrt(a)) do
   if a mod i<>0 then inc(i)
    else begin
        inc(k);
         p[k].fact:=i; s:=0;
            repeat
             inc(s);
              a:=a div i;
            until (a=1) or (a mod i<>0);
          p[k].put:=s*q;
          inc(i);
          end;
 if a>1 then begin p[k+1].fact:=a; p[k+1].put:=q; n:=k+1; end
 else n:=k;
end;
procedure cauta(l,r:longint);
 var mid,k:longint;
     j:int64;
begin
j:=p[i].fact; k:=0;
 mid:=(l+r) div 2;
 while trunc(mid/j)>0 do begin
                     k:=k+trunc(mid/j);
                     j:=j*j;
                     end;
if l<>r then begin
if k>=p[i].put then cauta(l,mid-1)
 else if k<p[i].put then cauta(mid+1,r);
               end
 else begin
        if k>=p[i].put then b:=mid
         else b:=mid+1;
 end;
end;

procedure get_fact();
begin
 for i:=1 to n do begin
   cauta(1,p[i].put*p[i].fact);
    if b>max then max:=b;
      end;
end;
begin
 assign(fi,'gfact.in');
  assign(fo,'gfact.out');
 reset(fi); rewrite(fo);
 readln(fi,a,q);
  descompune();
   get_fact();
 write(fo,max);
close(fo);
end.