Cod sursa(job #759873)
program fractii;
type s1=array [1..1000000] of real;
s2=array [1..1000000] of integer;
var f,g:text;
d,suma,n,cop,p:integer;
i,j:longint;
a:s1;
t:s2;
begin
assign(f,'fractii.in');reset(f);
assign(g,'fractii.out');rewrite(g);
read(f,n);
for i:=2 to n do
if a[i]=0 then
for j:=2 to (n div i) do
a[i*j]:=1;
suma:=1;
for i:=1 to n do
begin
if a[i]=0 then t[i]:=i-1
else
begin
d:=2;
while i mod d<>0 do
inc(d);
p:=1;
cop:=i;
while cop mod d=0 do
begin
cop:=cop div d;
p:=p*d;
end;
if cop=1 then t[i]:=i-(i div d)
else t[i]:=t[p]*t[cop];
end;
suma:=suma+t[i];
end;
write(g,2*suma-1);
close(f);
close(g);
end.