オイラーのφ関数(Euler's-Phi-Function)

説明

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

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

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

計算量

• $O(\sqrt N)$

実装例

• euler_phi($n$): $\phi(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;
}

検証

AOJ NTL_1_D オイラーのφ関数

#define PROBLEM "http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=NTL_1_D"

#include "../../template/template.cpp"

#include "../euler-phi.cpp"

int main() {
  int N;
  cin >> N;
  cout << euler_phi(N) << endl;
}