Euler's totient function (オイラーのφ関数)
(math/prime/euler_totient.hpp)

• View this file on GitHub
• Last update: 2020-04-22 01:00:48+09:00
• Include: #include "math/prime/euler_totient.hpp"

概要

$1$以上$N$以下の整数について, $N$と互いに素なものの個数を求める.

計算量

$O(\sqrt{n})$

使用例

• euler_totient(N) : $\varphi(N)$を返す.
  • 返り値の型 : long long

Verified with

• test/aoj/NTL_1_D.test.cpp

Code

/**
* @brief Euler's totient function (オイラーのφ関数)
* @docs docs/math/prime/euler_totient.md
*/

long long euler_totient(long long n) {
    long long ret = n;
    for (long long i = 2; i * i <= n; ++i) {
        if (n % i) continue;
        ret -= ret / i;
        while (n % i == 0) n /= i;
    }
    if (n > 1) ret -= ret / n;
    return ret;
}

#line 1 "math/prime/euler_totient.hpp"
/**
* @brief Euler's totient function (オイラーのφ関数)
* @docs docs/math/prime/euler_totient.md
*/

long long euler_totient(long long n) {
    long long ret = n;
    for (long long i = 2; i * i <= n; ++i) {
        if (n % i) continue;
        ret -= ret / i;
        while (n % i == 0) n /= i;
    }
    if (n > 1) ret -= ret / n;
    return ret;
}

Back to top page