第３話 素数探索はいかにしたらマルチ化できるか？

素数にはとても面白い性質があります。

素数を例えば５で割った余りで分類するとします。
５以外の素数は、５で割ったときの余りが
１の場合、２の場合、３の場合、４の場合
の４つの場合に分かれます。
５以外の素数を
２，３，７，１１，１３，１７，１９，２３，２９，３１，・・・
５で割っていくとそれぞれの余りは、
２，３，２，１，３，２，４，３，４，１，・・・
ですね。
ですから、
５で割ったときの余りが１のグループ・・・１１，３１，４１，６１，・・・・
５で割ったときの余りが２のグループ・・・２，７，１７，３７，・・・・
５で割ったときの余りが３のグループ・・・３，１３，２３，４３，・・・・
５で割ったときの余りが４のグループ・・・１９，２９，３９，５９，・・・・
と、５以外の素数を４分類することが出来るわけです。
では、４グループの素数の現れる割合は、
異なるのでしょうか。
実は、どのグループにも全く同じ頻度で素数が現れるのです。

今は、５で割った余りで分類しましたが、
７で割って６分類することも出来ます。
この６分類にも素数は、同じ割合で登場します。
さらに、
１１で割って１０分類しても同じ割合で素数は現れます。
１７で割って１６分類しても同じ割合で素数は現れます。
１９で割って１８分類しても同じ割合で素数は現れます。
　　　　　　・・・
　　　　　　・・・
　　　　　　・・・
1999993で割っ余て、1999992分類しても同じ割合で素数は現れます。
（神は1999992面をもつサイコロを振って、素数を割り振っているのです。）
　　　　　　・・・
　　　　　　・・・
　　　　　　・・・


どの分類にも同じ割合で素数が現れる･･･
これは、割る数をいかに大きくしていっても成り立つのです。


皆さん、お気づきですね。
分類するときに割る数は!?
３，５，７，１１，１３，１７，１９，・・・・
そうです。
素数です。

ということは、
６スレッド化するには、素数を
７で割ったときに余りが１になる素数、
７で割ったときに余りが２になる素数、
７で割ったときに余りが３になる素数、
７で割ったときに余りが４になる素数、
７で割ったときに余りが５になる素数、
７で割ったときに余りが６になる素数
に６分類し、
それぞれの分類をそれぞれのスレッドに探索させれば、
６スレッド探索が可能になります。