オイラーのφ関数
(library/number/prime/euler_phi.hpp)

• View this file on GitHub
• Last update: 2026-01-22 14:26:48+09:00
• Include: #include "library/number/prime/euler_phi.hpp"

オイラーのφ関数

できること

• 正の整数Nが与えられたとき、1~Nまでの自然数のうちNと互いに素な個数 $\phi (N)$ を求める
• $\phi (n) = n \displaystyle\prod_{i=1}^{k} (1 - \frac{1}{p_i})$

計算量

$O(\sqrt{N})$

使い方

long long ans = euler_phi(N);

Required by

• テトレーション (library/number/mod/mod_tetration.hpp)

Verified with

• MOD テトレーションのテスト (tests/number.mod.mod_tetration.test.cpp)
• エラトステネスの篩のテスト (tests/number.prime.eratosthenes.test.cpp)

Code

#pragma once
template <typename T> T euler_phi(T n) {
    T ret = n;
    for (T i = 2; i * i <= n; ++i) {
        if (n % i == 0) {
            ret -= ret / i;
            while (n % i == 0) n /= i;
        }
    }
    if (n > 1) ret -= ret / n;
    return ret;
}

#line 2 "library/number/prime/euler_phi.hpp"
template <typename T> T euler_phi(T n) {
    T ret = n;
    for (T i = 2; i * i <= n; ++i) {
        if (n % i == 0) {
            ret -= ret / i;
            while (n % i == 0) n /= i;
        }
    }
    if (n > 1) ret -= ret / n;
    return ret;
}

Back to top page