ei1333's page

オイラーのφ関数

説明

正の整数 $n$ に対して, $1$ から $n$ までの自然数のうち $n$ と互いに素なものの個数を $\phi(n)$ として与えることに酔って定まる数論的関数 $\phi$ である。

計算量

値 $O(\sqrt N)$

テーブル $O(N \log \log N)$

実装例

int64_t euler_phi(int64_t n) {
  int64_t ret = n;
  for(int64_t i = 2; i * i <= n; i++) {
    if(n % i == 0) {
      ret -= ret / i;
      while(n % i == 0) n /= i;
    }
  }
  if(n > 1) ret -= ret / n;
  return ret;
}

vector< int > get_euler_phi(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;
}