素数表作成

1. 素数表は正しいのでしょうか?

 エラトステネスの篩(ふるい)の考え方に沿って、本当にアルゴリズムがうまくできているか? といってもいいでしょう。

 結論を先に言うと、1011迄はまともに動いています。素数の個数を求めた作業で、専門の電算屋さんが出しているサイトなのでしょうか1022迄求めた物凄いデータの中の記載 ( http://www.utm.edu/research/primes/howmany.shtml#contents )と一致した(4,118,054,813)ので、他力本願ですが、万に一つも間違っていることは無いだろうと踏んでいます。

 

2. 一般的にどんな風に作るのでしょう

 C言語などで、練習で素数を求める場合は、1つの数を1 byte(8 bits)又は、1 word(16 bits)に割り当ててテーブルを作り、全データを1(素数)としてから、最初の1に該当するデータを0(非素数)に変えます。この表で、1に最も近い素数2を求め、その数字2をリストに出力します。2から始めて、2番目ごとの4, 6, 8,・・・を順繰りに、データを0(非素数)に変えます。この時点で、偶数でデータが1となっているのは、2だけです。

 次に、2のすぐ後に続く データが1の数(素数) 3を求め、これもリストに出力し、そこから3番目ごとの、6, 9, 12,・・・のデータを0(非素数)にし、という具合に操作します。3の次の素数を求めにいくと、すぐ次の4が既に非素数になっているので、次の5をリストアップしてから、後続の5の倍数を非素数化、といった具合です。

 

3. どんな工夫をしたのでしょう(こんなのは常識、という部分も多々ありますが列挙しました)

3.1. データサイズ

 先ず、1つの数値に割り当てるべきデータサイズですが、10かをセットするだけだから1 bitで十分です。よりコンパクトなサイズでより高速演算を求めれば、それ以外は無用の長物になります。

 例えば、検索用素数を求めた後、その素数の倍数を全部非素数化する作業で、ビットパターンで処理することができます。

3.2. 素数は1 ? 0

 素数と非素数を各々01のどちらに割り付けるかは、プログラムを作成する人が決めることで、やり易いように勝手に決めればいいことです。

3.3. 偶数は如何する

偶数のチェックですが、偶数の素数は2だけと誰でも知っているので、実作業では偶数を全部外して、テーブルの大きさを半分にします。素数リストへ2を出力するだけ(個数を数えるときは、1個カウント済み)で、3からの作業へ進めます。偶数を外しただけの表は規則性がいいので、例えば3から数えて3つ目は9次が15でやはり3の倍数としての処理が可能です。

 それなら、3の倍数も全部外した状態からすればもっと良さそうですが、これは規則性が悪く 煩雑になるだけで、作業ができません。

3.4. テーブルサイズは

 何種類かやってみましたが、5bits50bitsがいいところでしょう。奇数だけを相手にするので、10万までにするか、100万までにするか、というところです。

3.5. いくつまで求めることができるか(何故? についてはいずれ解説します)

 テーブルサイズが直接影響します。通常のやり方では、10万までのテーブルであれば、それを基に10万ページ分のテーブルを、作りながら作業することができます。(105)2=1010即ち、100億までです。もっと大きな素数を検索するには、より大きなテーブルが必要で、100万までのテーブルで、1兆まで求めることができる筈です。因みに、100億までの素数の個数を数えるだけで、80秒かかるとして、1000億なら、恐らく20分くらい。1兆なら5時間くらいかかるのではないでしょうか?

3.6. それ以上の数に対する試み

 実は、これに関連して、同じ篩を使って大きな数を素因数分解するプログラムを作りましたが、理屈の上では1024までの数値が、素数であるかどうかをチェックできます。でも、1024レベルの数値を小さな素数から順番に割り算する作業を考えたら、それだけで数日かかりそうです。

3.7. プログラム言語は

 骨格部分は、C言語を使いました。C++なのですが、殆どCそのものみたいな使い方です。ただ、Cは余り早くないので、繰り返し作業の多い部分はアセンブラを使っています。その結果として恐らくC単独と較べて1桁以上速くなっている筈です。

3.8. 0ページ目の作業(最初は、1ページとして書き始めましたが、説明の都合で、0ページ」と変更します)

 ところで、0ページ目の作業のイメージが理解できるほど、まだ説明ができていません。表の大きさですが、例えば1ページの大きさを10万までと決めます。その結果、奇数だけで、5bitsデータ領域を準備します。1 byte = 8 bits ですから、6250 bytes = 3125 words の領域を準備します。

 蛇足ですが、データの置き場(アドレス)は、最初を0 byte目と呼び、その中を、07 bit 目と呼びます。この呼び方は、説明する人のそのときの気分で、1から始めることもありますが、0から始めた方が辻褄合わせし易いようです。素数扱いしない1の置き場は 0 byte 目の中の第0 bitになります。最初の奇素数3が第1 bitになります。1 byte 目の中の第0 bit17の置き場です。

3.9. 新しい素数で検索するたびに

 素数3をリストアップし、次から3つ目毎に消し込む検索作業が、テーブルの最後まで済んだとします。次は5の作業になります。篩い分けは幾つから始めたらいいでしょう。消し込み作業は、55=25から始めれば十分です。これはプログラム作成上面倒くさい作業ですが、検索用の素数が大きくなるにつれて、無用な作業を削減してくれます。

 ここで、小さいほうから素数を抑えては、その倍数を消し込んでいくのでした。5の倍数の消し込みが済んだ時点で、次の素数7の、26倍は、作業が済んでいるので、7倍の、72=49から始めることになるのでした。49を管理するデータ置き場は、(49-1)/2=24 24/8=3なので、3 byte 目の中の第0 bitになります。この作業をSQRT(10)となる316より小さな素数全部で消し込めば、消されずに残った数が、全部素数です。

3.10. 1ページ目以降の作業(2ページとして書き始めましたが、説明の都合で、1ページ」と変更

0ページ目の作業は単純だけど、1ページ目の3の倍数は何処から始まり、5, 7, 11, 13 の倍数はどうなるの? という話でした。暫らく遠ざかっていたプログラムを見る作業も大仕事になりそうなので、計算式(アルゴリズム)を作り直しました。

テーブルの大きさをm=5bitとし、10万までを管理する場合とします。ページ数も、最初の0ページ目に対して、99,999ページまで作ることになりますが、そのnページ目の作業とします。そのときの素数pに対するトータルbit アドレスが、mod((p-1)/2-n*m ,) で与えられます。この値がもし、負の数で与えられる計算方式なら、mod((p+1)/2-n*m ,)+p-1 とします。 8で割れば、byteアドレスで、余りがbit順位です。この面倒くさい計算うまく作り上げれば、処理はパソコンがやってくれます。これを、高速処理してくれるアセンブラで組んだ次第です。

 

3.11. 他にどんなことがあるでしょう

細かいことまで言えばきりが無いほどあります。テクニックは色々です。

取り敢えず、今日は、この辺で筆を置きます。続きは、また気が向いたときです。