オイラーのトーティエント関数の値の列挙

目的

オイラーのトーティエント関数$\phi(i)=$($1,...,i$のうち$i$と互に素な整数の個数)について、$\phi(i)$の$i=1,...,n$の値を列挙します。

計算量

$O(n \log \log n)$

使い方

int[] phi
phi[i]にオイラーのトーティエント関数にiを代入した値をreturn

ソースコード

int n;
int[] phi=new int[n]
for (int i = 2; i < phi.length; ++i) {
	phi[i] = i;
}
for (int i = 2; i < phi.length; ++i) {
	if (phi[i] != i)
		continue;
	for (int j = i; j < phi.length; j += i) {
		phi[j] = phi[j] / i * (i - 1);
	}
}