const nmax=200000;pmax=1e14;
var prim:array[1..nmax]of longword;
    n,p,sol:qword;
    k:longword;

procedure citire;
begin
assign(input,'frac.in');reset(input);
readln(n,p);
close(input);
end;

procedure precalc;
var f:longword;n1:qword;
begin
k:=0;
f:=2;
n1:=n;
while (n1>1)and(f<=sqrt(n1)) do
 begin
  if n1 mod f=0 then
  begin
  while n1 mod f=0 do n1:=n1 div f;
  inc(k);
  prim[k]:=f;
  end;
 inc(f);
 end;
if n1>1 then begin inc(k);prim[k]:=n1;end;
end;

function valid(m:qword):boolean;
var i:longword;j,nr:byte;
    prod:qword;rez,fact:int64;
begin
fact:=0;
for i:=1 to 1 shl k-1 do
 begin
 nr:=0;prod:=1;
 for j:=0 to k-1 do if (i shr j)and 1=1 then
  begin
  inc(nr);
  prod:=prod*prim[j+1];
  end;
 if odd(nr) then inc(fact,m div prod) else dec(fact,m div prod);
 end;
rez:=m-fact;
if rez<p then valid:=true
         else valid:=false;
end;

procedure cautare;
var j:qword;
begin
j:=1 shl 61;sol:=0;
repeat
while (not valid(sol+j))and(j<>0) do
 begin
 j:=j shr 1;
 end;
inc(sol,j);
j:=j shr 1;
until j=0;
end;

procedure afisare;
begin
assign(output,'frac.out');rewrite(output);
writeln(sol+1);
close(output);
end;

begin
citire;
precalc;
valid(6);
cautare;
afisare;
end.