Euler's Totient Function（オイラーのトーシェント関数）
(algorithm/Math/NumberTheory/totient.hpp)

• View this file on GitHub
• Last update: 2025-08-30 05:48:04+00:00
• Include: #include "algorithm/Math/NumberTheory/totient.hpp"

概要

自然数 $n$ に対して，$n$ と互いに素である $1$ 以上 $n$ 未満の自然数の個数を求める．

\[\varphi(n) = \sum_{\substack{1 \leq m < n \\ \gcd(m,n) = 1}} 1.\]

「オイラーの $\varphi$ 関数」とも呼ぶばれる．

参考

1. “オイラーのφ関数”. Wikipedia. https://ja.wikipedia.org/wiki/オイラーのφ関数.
2. “オイラー関数の定義・性質4つとその証明”. 数学の景色. https://mathlandscape.com/euler-function/.

Depends on

• 素因数分解 (algorithm/Math/NumberTheory/prime_factorize.hpp)

Code

#ifndef ALGORITHM_TOTIENT_HPP
#define ALGORITHM_TOTIENT_HPP 1

#include <cassert>
#include <concepts>
#include <cstdint>
#include <ranges>
#include <type_traits>

#include "prime_factorize.hpp"

namespace algorithm {

namespace internal {

template <std::ranges::range R>
    requires std::is_integral_v<std::ranges::range_value_t<R>>
constexpr std::uint64_t totient(std::uint64_t n, const R &factors) {
    for(auto p : factors) n = n / p * (p - 1);
    return n;
}

constexpr std::uint64_t totient(std::uint64_t n) { return totient(n, ::algorithm::internal::distinct_prime_factorize<std::uint64_t>(n)); }

}  // namespace internal

// オイラーのトーシェント関数．nと互いに素であるn未満の自然数の個数を求める．
template <std::integral Type>
constexpr std::uint64_t totient(Type n) {
    assert(n > 0);
    return internal::totient(n);
}

}  // namespace algorithm

#endif

#line 1 "algorithm/Math/NumberTheory/totient.hpp"



#include <cassert>
#include <concepts>
#include <cstdint>
#include <ranges>
#include <type_traits>

#line 1 "algorithm/Math/NumberTheory/prime_factorize.hpp"



#include <algorithm>
#include <bit>
#line 9 "algorithm/Math/NumberTheory/prime_factorize.hpp"
#include <map>
#include <vector>

namespace algorithm {

namespace internal {

template <std::integral Res>
constexpr std::vector<Res> distinct_prime_factorize(std::uint64_t n) {
    std::vector<Res> factors;  // factors[]:=(自然数nの素因数のリスト).
    factors.reserve(15);
    if(n % 2 == 0) {
        factors.push_back(2);
        auto c = std::countr_zero(n);
        n >>= c;
    }
    for(std::uint64_t p = 3; p < 1ULL << 32 and p * p <= n; p += 2) {
        if(n % p != 0) continue;
        factors.push_back(p);
        do {
            n /= p;
        } while(n % p == 0);
    }
    if(n > 1) factors.push_back(n);
    return factors;
}

template <std::integral Res>
std::map<Res, int> prime_factorize(std::uint64_t n) {
    std::map<Res, int> res;  // res[p]:=(自然数nに含まれる素因数pの個数).
    if(n % 2 == 0) {
        auto c = std::countr_zero(n);
        res.emplace_hint(res.end(), 2, c);
        n >>= c;
    }
    for(std::uint64_t p = 3; p < 1ULL << 32 and p * p <= n; p += 2) {
        int c = 0;
        while(n % p == 0) n /= p, ++c;
        if(c > 0) res.emplace_hint(res.end(), p, c);
    }
    if(n > 1) res.emplace_hint(res.end(), n, 1);
    return res;
}

}  // namespace internal

// 自然数nの素因数を求める．O(√n).
template <std::integral Type>
constexpr std::vector<Type> distinct_prime_factorize(Type n) {
    assert(n > 0);
    return internal::distinct_prime_factorize<Type>(n);
}

// 素因数分解．O(√n).
template <std::integral Type>
std::map<Type, int> prime_factorize(Type n) {
    assert(n > 0);
    return internal::prime_factorize<Type>(n);
}

// 高速約数列挙．
template <typename Type>
std::vector<Type> divisors(const std::map<Type, int> &pf) {
    std::vector<Type> divs({1});
    for(const auto &[p, c] : pf) {
        const int sz = divs.size();
        Type d = 1;
        for(int i = 0; i < c; ++i) {
            d *= p;
            for(int j = 0; j < sz; ++j) divs.push_back(divs[j] * d);
        }
    }
    divs.shrink_to_fit();
    std::sort(divs.begin(), divs.end());
    return divs;
}

}  // namespace algorithm


#line 11 "algorithm/Math/NumberTheory/totient.hpp"

namespace algorithm {

namespace internal {

template <std::ranges::range R>
    requires std::is_integral_v<std::ranges::range_value_t<R>>
constexpr std::uint64_t totient(std::uint64_t n, const R &factors) {
    for(auto p : factors) n = n / p * (p - 1);
    return n;
}

constexpr std::uint64_t totient(std::uint64_t n) { return totient(n, ::algorithm::internal::distinct_prime_factorize<std::uint64_t>(n)); }

}  // namespace internal

// オイラーのトーシェント関数．nと互いに素であるn未満の自然数の個数を求める．
template <std::integral Type>
constexpr std::uint64_t totient(Type n) {
    assert(n > 0);
    return internal::totient(n);
}

}  // namespace algorithm

Back to top page