オイラーの φ 関数

$N$ を割り切る素数を $p_1, \ldots, p_k$ とすると $\varphi(N) = N (1 - 1/p_1) \cdots (1 - 1/p_k)$ であることを使います。

• euler_phi(N): $\varphi(N)$（ $N \ge 1$）。試し割りで素因数を求める。 $O(\sqrt{N})$
• phi_table(N): phi[x] が $\varphi(x)$ になるリスト（ $0 \le x \le N$、phi[0] は $0$）を返す。篩で、素数 $p$ の倍数をまとめて処理する。 $O(N \log \log N)$

$a$ と $N$ が互いに素なとき $a^{\varphi(N)} \equiv 1 \pmod{N}$ が成り立ちます（オイラーの定理）。また、分母が $N$ の既約分数で $0$ より大きく $1$ 以下のものは $\varphi(N)$ 個あります。

コード

def euler_phi(n):
    # 1 以上 n 以下で n と互いに素な整数の個数
    res = n
    p = 2
    while p * p <= n:
        if n % p == 0:
            res -= res // p
            while n % p == 0:
                n //= p
        p += 1
    if n > 1:
        res -= res // n
    return res


def phi_table(n):
    # phi[x] = φ(x)（0 <= x <= n、phi[0] = 0）
    phi = list(range(n + 1))
    for p in range(2, n + 1):
        if phi[p] == p:  # p は素数
            for x in range(p, n + 1, p):
                phi[x] -= phi[x] // p
    return phi