phiFunction

Euler's φ function is defined as φ(n):=# of positive integers ≤ n that are coprime with n. φ(1)=1, p prime ⇒ φ(p^k)=(p-1)p^k-1, m,n coprime ⇒ φ(mn)=φ(m)φ(n). If n=p_1^k_1p_2^k_2 ... p_r^k_r then φ(n) = (p_1-1)p_1^k_1-1...(p_r-1)p_r^k_r-1. φ(n)=n · Π_p|n(1-1/p). Σ_d|n φ(d) = n, Σ_1≤ k ≤ n, gcd(k,n)=1 k = n φ(n)/2, n>1 Euler's thm: a,n coprime ⇒ a^φ(n) ≡ 1 (mod n). Fermat's little thm: p prime ⇒ a^p-1 ≡ 1 (mod p) forall a.

8 lines Tested

content/number-theory/phiFunction.h — Håkan Terelius, source: http://en.wikipedia.org/wiki/Euler's_totient_function

const int LIM = 5000000;
int phi[LIM];

void calculatePhi() {
	rep(i,0,LIM) phi[i] = i&1 ? i : i/2;
	for (int i = 3; i < LIM; i += 2) if(phi[i] == i)
		for (int j = i; j < LIM; j += i) phi[j] -= phi[j] / i;
}