『オイラーのトーシェント関数 50000』できた

オイラーのトーシェント関数 50000

Euler's totient function (English Edition)

　簡単に言えば、nはn以下の数全部と比べて互いに素な数は何個ありますか？という話。

互いに素

　互いに素っていうのは、公約数が1しかない数のこと。
例えば、12と11はそれぞれ1でしか割れないので互いに素。
12と8だと、それぞれ1,2,4,で割れてしまうので、互いに素じゃない。

オイラーのトーシェント関数

　戻って、n以下で互いに素な数の個数、というと
例えば10の場合、10,9,8,7,6,5,4,3,2,1のうち10と互いに素なのは何か？
10と10だと、公約数は1,2,5,10なので10は互いに素じゃない。
10と1では、公約数は1だけなので互いに素。
というわけで見ていくと、1,3,7,9が互いに素な数になる。よって4個。
10の場合は4、と決まる。

　それをバーッと50000まで調べた。

　んでいつも通り、作った後にもっと簡単に調べる方法を思いつくっていうね……。

ルート47 1000000桁

オイラーのトーシェント関数 50000

1×1, 11×11, 111×111, ……