NKABD - Số phong phú
Tác giả: RR
Ngôn ngữ: Pascal
const
MAXN = 100000;
var
lt,m,p : array[1..MAXN] of longint;
sum : array[1..MAXN] of int64;
procedure init;
var
i,gh,j,u:longint;
begin
gh:=trunc(sqrt(MAXN));
for i:=1 to MAXN do
begin
p[i]:=i;
lt[i]:=1;
m[i]:=1;
end;
for i:=2 to gh do
if p[i]=i then
begin
j:=i*i; u:=i;
while (j<=MAXN) do
begin
p[j]:=i;
m[j]:=u;
while m[j] mod i=0 do
m[j]:=m[j] div i;
if m[j]=1 then lt[j]:=lt[u]+1
else lt[j]:=0;
inc(j,i); inc(u);
end;
end;
sum[1]:=0;
for i:=2 to MAXN do
if lt[i]=0 then sum[i]:=sum[m[i]]*sum[i div m[i]]
else sum[i]:=(int64(i)*p[i]-1) div (p[i]-1);
end;
var
i,l,r,cnt:longint;
begin
init;
read(l,r);
for i:=l to r do
if sum[i]-i>i then inc(cnt);
writeln(cnt);
end.