线性筛一下欧拉函数，然后加起来×2加3即可。
program p2190; var x:array[1..400000] of boolean; prime,phi:array[1..400000] of longint; len,n,i,j,tot:longint; begin readln(n); dec(n); fillchar(x,sizeof(x),false); len:=0; for i:=2 to n do begin if x[i]=false then begin inc(len); phi[i]:=i-1; prime[len]:=i; end; j:=1; while (j<=len) and (prime[j]*i<=n) do begin x[i*prime[j]]:=true; if i mod prime[j]=0 then begin phi[prime[j]*i]:=phi[i]*prime[j]; break; end else phi[prime[j]*i]:=phi[i]*(prime[j]-1); inc(j); end; end; tot:=0; for i:=1 to n do tot:=tot+phi[i]; tot:=tot*2+3; writeln(tot); end.
