オイラーの関数φ(n)とは、1からnまでの整数のうちnと互いに素なものの個数のこと。

たとえば、1,2,3,4,5,6のうち6と互いに素なのは、1,5の二つなので、φ(6)=2。素数pについては、1からpまでの整数のうち互いに素でないのはp自身だけなので、φ(p)=p-1となることは直ちに理解できよう。なお、φ関数は英語では、totient functionと呼ばれている。

1からのφ関数の値は以下の通り。

 1, 1, 2, 2, 4, 2, 6, 4, 6, 4, 10, 4, 12, 6, 8, 8, 16, 6, 18, 8, 12

φ(n)の計算に重要なもの(性質)をいくつかピックアップしておく。

totient.jpg

整数の素因数分解と同様、個々のφ(n)の計算と、多数のnのφ(n)の計算とを分けて、その計算法を考えよう(数学ではそんなことを考える必要性は全くないが)。

個々のφ(n)の計算では、nの素因数分解を利用する方法が最も効率的だろう。nに含まれている素因数pkが分かれば、(n/Pk)*(pk-1)で計算していけばよし。

多数のnをまとめてそのφ(n)を計算するなら、以下のプログラムを利用しよう。φ(n)の性質(互いに素)を利用した方法。

これでいっぺんに、MAX(100万)までの値が計算される。

Comments are closed.

Post Navigation