https://codeiq.jp/ace/ozy_hikoboshi/q961

7777777buffalo.cs

using System;
using System.Collections;
using System.Collections.Generic;

class TEST{
	static void Main(){
		
		long N=7777777;
		long ans=3;
		
		long[] Totient=new long[N];
		for(int i=0;i<N;i++)Totient[i]=i;
		
		
		for(int i=2;i<N;i++){
			if(Totient[i]==i){
				for(int j=i;j<N;j+=i){
					Totient[j]=Totient[j]/i*(i-1);
				}
			}
			ans+=2*Totient[i];
		}
		
		Console.WriteLine("{0}",ans);
	}
}

回答

（ポイント１）
X以下の互いに素な整数の個数は、オイラーのtotient関数φとして知られていて
Xの素因数分解　X=Πp_k^e_k　{p_k}素因数／{e_k}次数
に対して、 φ(X)=X*Π(p_k-1)/p_k  で求めることができる。

各Xに対してφ(X)を素直に計算すると 計算量は O(X^0.5)なので、
N=7777777だと 計算量は
(√2 + √3 + √4 +・・・+√N-1)
で　O(N^1.5)　となる。

（ポイント２）
エラトステネスの篩の要領で、Xが素数の時に、X以上のXの倍数に
フィードフォワードする。
X<X'がXを素因数に持つなら、X'をXで割ってX-1をかける操作を行うため、
Xが素数の場合にはX以上のXの倍数にすべてその処理をすればよい。
Xが素数であるかは、Xより小さい数からのフィードフォワードを受けているかでわかる。

このアルゴリズムの場合、計算量は
(N/2 + N/3 + N/4 +・・・+N/(N-1) )　　※（Xが合成数の部分はフィードフォワードしないのでもっと小さい） 
で抑えられ、O(NlogN)程度になる。


手元の環境（Visual C# 4.0／ Intel Core i7/3.2GHz/64bitOS）で
ポイント１の処理時間　53498[msec]
ポイント２の処理時間　939[msec]
でした。（計算量オーダーを読み間違っている気がしないでもない。。。）