素数、友愛数を求める
以前、こんな記事を書いた。
三冊（チョコレートをたべたさかな、東京タワー、博士の愛した数式） - じゅんじゅんのきまぐれ
この中の「博士の愛した数式」で書いたプログラムについて。
年の瀬にプログラムを改造して、年明けからほとんど動かしっぱなし。
改造前は、素数をひたすら求めるだけ。
1000万まで行くのに、3日程度でしたが、改造後の現在は、
25日くらいで、500万程度。
えらい遅くなったので、早くするアイデアを募集中。
ということで、現在のロジックを書いてみる。
ロジックなんてのは、長く面白くないものであったりします。
随分遅くなったのは、以下の改造のため。
1.全ての素数は、本当に4n-1か4n+1か？
2.双子素数はどの程度発生するか？
3.友愛数を探す
どんな原理か記事にしてみる。
素数を探すだけのアルゴリズム
- 素数領域に、2と3を登録する
- 最初の検討数を5とする
- メイン部：
- 次へ：
- 検討数を+2して、メイン部最初に戻る
解説
2と3は、とりあえず素数。
4は素数でない。これは算出しない。
よって、最初の検討数は、5とする。
素数以外で割れるか検討しないのは、必要ないから。
例えば、121で割り切れる数は、121を割り切れる素数、11でも当然割り切れる。
なお、素数領域にある数全てで検査しなくても良い。
正確には、検討数の平方根以下の数、すなわち、検討数が144の場合、12までの素数で検査すれば良い。
次へ、で+2するのは、偶数は検討するまでもないから。
2以外の素数は、奇数のみ。
改造後のプログラム
1.全ての素数は、本当に4n-1か4n+1か？
これは、見つけた素数が、1足して4で割り切れるか、1引いて4で割り切れるか見る。
これを、素数を発見した部分に加えるだけ。
、、、なのですが、、、先日、はたと気付いた。
計算するまでもない！
何故なら、全ての自然数は4で割り切れる数を中心に考えると、
4n, 4n+1, 4n+2, 4n+3 の4つに分類できる。
そして、4n-1 に分類できる数と、4n+3 に分類できる数は同じもの。
ということは、本の中で素数候補とされた数は、4n+1 と 4n+3。
素数候補以外の数は、4n と 4n+2。
4n と 4n+2 は、いずれも、2で割り切れる、、、偶数である、、、。
ということで、4n-1 か 4n+1 か検証ロジックは無駄である。
3.友愛数を探す
これが、最大負荷。
まず、+2で検討候補を加算していたのが、+1づつに修正。
それから、友愛数と友愛数相方領域を用意する。
（相方と同じ数値の場合、完全数、ということですな。）
素数でない、と判定した後に、友愛数相方領域にあるか確認。
あれば、検出済みで次の数値へ。
なければ、割り切れる値を全て割り出す。（素数以外も）
割り切れる値の場合、それらを加算して回る。
半分までの数値で、割り切れる数を洗い終わったら、加算結果が元の数値より同じか大きいか確認。
同じ場合、完全数として登録。
大きい場合、加算結果の割り切れる数の合計を洗う。
合計値が検討数と同じになったら、友愛数として登録。
重い。
奇数しか検討しない。
素数で割り切れるか確認すれば良い。
それも検討数の平方根まで。
元のプログラムを作るときに思いついた高速化が、全てぱー、です。
うちのPCは、Pen4のHyperthreadテクノロジ。*1
なので、動かしっぱなしでも、特に問題はないですけどね。
ブログ更新中も計算。
メール書いてる間も計算。
OSのUpdate中も計算。
Hyperthreadテクノロジ、デスクトップPCには良いですね。
何かさせつつ、私の相手もしてもらう。
フォン・ノイマンこんぴーた、偉いの。
*1:二つの作業をほぼ同時処理できる技術のこと。計算処理と私の相手と二つの処理、ということ
