program gfact;
var p,q:longint;
        f,g:text;
        divizor,putere:longint;
        cr:array[1..2000000001] of boolean;


procedure ciur;
var i,n,j:longint;
begin
        n:=p;
        i:=2;
        fillchar(cr,sizeof(cr),false);
        while 1>0 do
                begin
                        j:=i;
                        while (cr[j]=false)and(j<=n) do
                                inc(j);
                        if j>n then
                                break else i:=j;
                        for j:=1 to n div i do
                                cr[i*j]:=true;
                end;
        divizor:=i;
        i:=0;
        while n mod divizor=0 do
                begin
                        inc(i);
                        n:=n div divizor;
                end;
        putere:=i*q;
end;


procedure iofile;
var d,e:longint;
begin
        assign(f,'gfact.in');
        reset(f);
        assign(g,'gfact.out');
        rewrite(g);
        readln(f,p,q);
        ciur;
        close(f);
end;





procedure prel;
var i:longint;
        put,x,d,diviz:longint;
begin
        put:=0;
        i:=0;
        x:=1;
        diviz:=1;
        while x<=putere do
                begin
                x:=x*divizor+1;
                diviz:=diviz*divizor;
                end;
        x:=(x-1)div divizor;
        diviz:=diviz div divizor;
        while putere>0 do
                begin
                        i:=i+(putere div x)*diviz;
                        putere:=putere mod x;
                        x:=(x-1)div divizor;
                        diviz:=diviz div divizor;
                end;
        writeln(g,i*divizor);
        close(g);

end;



begin
        iofile;
        prel;
end.