NONAME PASCAL

type long=int64;
     int=longint;
     pf=record e, k: long; end;

var p: array[1..1000000] of pf;
    n, m, k: long;
    l: int;

procedure primefactor(m: long);
var d, lim: long;
begin
    l:=0;
    d:=2;

        if m mod d=0 then begin
            l:=l+1;
            p[l].e:=d;
            p[l].k:=0;
            while m mod d=0 do begin
                m:=m div d;
                p[l].k:=p[l].k+1;
            end;
        end;

    lim:=trunc(sqrt(m));
    d:=3;

    while d<=lim do begin
        if m mod d=0 then begin
            l:=l+1;
            p[l].e:=d;
            p[l].k:=0;
            while m mod d=0 do begin
                m:=m div d;
                p[l].k:=p[l].k+1;
            end;
            lim:=trunc(sqrt(m));
        end;

        d:=d+2;
    end;

    if m<>1 then begin
        l:=l+1;
        p[l].e:=m;
        p[l].k:=1;
    end;
end;

function calc(n, d: long):long;
var x: long;
begin
    calc:=0;
    x:=d;
    while d<=n do begin
        calc:=calc+n div d;
        d:=d*x;
    end;
end;

procedure solve;
var x: long;
    i: int;
begin
    k:=2100000000;
    for i:=1 to l do begin
        x:=calc(n, p[i].e) div p[i].k;
        if k>x then k:=x;
    end;
end;

begin
    readln(n, m);
    primefactor(m);
    solve;
    writeln(k);
end.