var n,b,a,k,nzerouri,d,m,sapnr,apnr,nr:longint;
    i:byte;
    f,g:text;
begin
assign(f,'zero2.in'); reset(f);
assign(g,'zero2.out'); rewrite(g);
for i:=1 to 10 do begin
  read(f,n,b);
  nzerouri:=1000000;
  a:=b;
  d:=2;
  while a<>1 do begin
    k:=0;
    while a mod d=0 do begin
      k:=k+1;
      a:=a div d;
    end;
    if k<>0 then begin
      m:=1;
      sapnr:=0; apnr:=0;
      nr:=m*d;
      repeat
        apnr:=(n-nr+1)*m; if apnr<0 then apnr:=0;
        sapnr:=sapnr+apnr;
        m:=m+1;
        nr:=m*d;
      until nr>n;
      if sapnr div k<nzerouri then nzerouri:=sapnr div k;
    end;
    d:=d+1;
  end;
  write(g,nzerouri);
  writeln(g); 
end;
close(g);
end.