Euler's Phi Function Table
(math/number-theory/EulersPhiFunctionTable.hpp)

• View this file on GitHub
• Last update: 2025-05-20 03:07:13+09:00
• Include: #include "math/number-theory/EulersPhiFunctionTable.hpp"

概要

todo

計算量

todo

Verified with

• verify/AizuOnlineJudge/math/number-theory/FareySequence2286.test.cpp

Code

vector<int> Eulers_phi_function_table(int n) {
  vector<int> table(n + 1);
  iota(table.begin(), table.end(), 0);

  for (int i = 2; i <= n; i++) {
    if (table[i] == i) {
      for (int j = i; j <= n; j += i) {
        table[j] = table[j] / i * (i - 1);
      }
    }
  }
  return table;
}

#line 1 "math/number-theory/EulersPhiFunctionTable.hpp"
vector<int> Eulers_phi_function_table(int n) {
  vector<int> table(n + 1);
  iota(table.begin(), table.end(), 0);

  for (int i = 2; i <= n; i++) {
    if (table[i] == i) {
      for (int j = i; j <= n; j += i) {
        table[j] = table[j] / i * (i - 1);
      }
    }
  }
  return table;
}

Back to top page