Problem 35

巡回素数っていう言葉があるんですね。
学術的に何かの役に立っている状況を想像することができませんが、
そんなことは気にせず解いてみます。


Problem 35

197は巡回素数と呼ばれる.
桁を回転させたときに得られる数
197, 971, 719 が全て素数だからである.
100未満には巡回素数が13個ある:
2, 3, 5, 7, 11, 13, 17, 31, 37, 71, 73, 79, および97である.
100万未満の巡回素数は何個か?


2桁以上の巡回素数は全ての桁の数字が 1, 3, 7, 9 の
いずれかである必要があるので、
100万未満の巡回素数は高々
5**6 = 15,625 個
しかありません。
そこで、これら全てについて素数判定を実行するというのが
1つの案として浮かびます。


上記の判定順序を逆にした案として、
エラトステネスのふるい法で素数を量産してから
その中で 1, 3, 7, 9 以外の数字が含まれているものを除外し、
それぞれが巡回素数かどうかを調べていく、
という方法もあります。


せっかくなので両方の速度を比較してみます。


…が!


どちらが速いか、あるいはもっと高速な方法で解いてみるか、
せっかくなのでチャレンジしてみてはいかがでしょうか。
と、問題提起風にして数少ない視聴者に話を振ってみました。
私の予想では前者が速いと思いますが、
正確に速度のオーダーを計算するなんていう仕事っぽいことはやりません。