オイラーのφ関数(Euler Phi)
(math/prime/eulerphi.cpp)

• View this file on GitHub
• Last update: 2026-03-22 19:39:35+09:00

説明

Euler の totient function phi(n) を 1 点で求める。 1 以上の整数 n と互いに素な 1..n の個数を返す。 計算量は $O(sqrt(n))$。

できること

• int eulerphi(int x) phi(x) を返す

使い方

x >= 1 を仮定する。 素因数分解しながら phi(n) = n Π (1 - 1/p) を適用する。

Verified with

• test/aoj_ntl_1_d_eulerphi.test.cpp

Code

int eulerphi(int x){
    int phi = x, xx = x;
    for (int i = 2; i * i <= x; ++i) {
        if (xx % i == 0) {
            phi -= phi / i;
            while(xx % i == 0) xx /= i;
        }
    }
    if(xx > 1) phi -= phi/xx;
    return phi;
}

/**
 * @brief オイラーのφ関数(Euler Phi)
 */

#line 1 "math/prime/eulerphi.cpp"
int eulerphi(int x){
    int phi = x, xx = x;
    for (int i = 2; i * i <= x; ++i) {
        if (xx % i == 0) {
            phi -= phi / i;
            while(xx % i == 0) xx /= i;
        }
    }
    if(xx > 1) phi -= phi/xx;
    return phi;
}

/**
 * @brief オイラーのφ関数(Euler Phi)
 */

Back to top page