Euler’s Phi Table(オイラーのφ関数テーブル) (math/number-theory/euler-phi-table.hpp)

• View this file on GitHub
• View document part on GitHub
• Last update: 2024-04-24 02:34:04+09:00
• Include: #include "math/number-theory/euler-phi-table.hpp"

概要

正の整数 $n$ が与えられたとき, $1$ から $n$ までの自然数のうち $n$ と互いに素なものの個数 $\phi(n)$ を求める.

以下の式で効率的に求めることができる.

$\phi(n)=n\displaystyle\prod_{i=1}^k(1-\dfrac{1}{p_i})$ (ただし $p_i$ は $n$ の素因数)

これは各素因数側から割っていっても同じように計算できるので, $n$ 以下のテーブルを効率的に構築可能である.

• euler_phi_table(n): n 以下のオイラーの $\phi$ 関数テーブルを返す.

計算量

• $O(N \log \log N)$

Verified with

• test/verify/aoj-2286.test.cpp

Code

/**
 * @brief Euler’s Phi Table(オイラーのφ関数テーブル)
 * 
 */
vector< int > euler_phi_table(int n) {
  vector< int > euler(n + 1);
  for(int i = 0; i <= n; i++) {
    euler[i] = i;
  }
  for(int i = 2; i <= n; i++) {
    if(euler[i] == i) {
      for(int j = i; j <= n; j += i) {
        euler[j] = euler[j] / i * (i - 1);
      }
    }
  }
  return euler;
}

#line 1 "math/number-theory/euler-phi-table.hpp"
/**
 * @brief Euler’s Phi Table(オイラーのφ関数テーブル)
 * 
 */
vector< int > euler_phi_table(int n) {
  vector< int > euler(n + 1);
  for(int i = 0; i <= n; i++) {
    euler[i] = i;
  }
  for(int i = 2; i <= n; i++) {
    if(euler[i] == i) {
      for(int j = i; j <= n; j += i) {
        euler[j] = euler[j] / i * (i - 1);
      }
    }
  }
  return euler;
}

Back to top page