math/totient-table.hpp

• View this file on GitHub
• Last update: 2023-07-08 14:12:19+09:00
• Include: #include "math/totient-table.hpp"

Depends on

• math/base.hpp

Code

#pragma once

#include "./base.hpp"

#include <vector>

namespace matumoto {
  vector<int> totient_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;
  }
} // namespace matumoto

#line 2 "math/totient-table.hpp"

#line 2 "math/base.hpp"

namespace matumoto {
  using namespace std;
  using ll = long long;
} // namespace matumoto
#line 4 "math/totient-table.hpp"

#include <vector>

namespace matumoto {
  vector<int> totient_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;
  }
} // namespace matumoto

Back to top page