src/math/number-theory/totient-table.hpp

• View this file on GitHub
• Last update: 2023-07-06 04:39:56+09:00
• Include: #include "src/math/number-theory/totient-table.hpp"

Code

#include <vector>
#include <numeric>

// calculate totient(i) (i \in [0, n])
// O(n loglog n)
std::vector<int> totient_table(int n){
  std::vector<int> ts(n+1);
  std::iota(ts.begin(), ts.end(),0);

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

#line 1 "src/math/number-theory/totient-table.hpp"
#include <vector>
#include <numeric>

// calculate totient(i) (i \in [0, n])
// O(n loglog n)
std::vector<int> totient_table(int n){
  std::vector<int> ts(n+1);
  std::iota(ts.begin(), ts.end(),0);

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

Back to top page