素数ベンチマーク
2011.04.16　Ver.0.002

2011.04.10　Ver.0.001　新規作成
2011.04.16　Ver.0.002　記事追加

第一節　はじめに

これまで、6n±1、30n+P、のエラトステネスの篩を考えてきました｡

ここで6n±1は２と３の倍数をのぞいた整数つまり、整数の中から選び出した素数候補を作る式です｡

整数は、2n、2n+1と書くことができます｡2nは2の倍数ですから2n+1が素数を含みます｡したがって、2-1です｡
また、整数は、3n、3n+1,3n+2とも書くことができます｡3nは3の倍数ですから3n+1,3n+2が素数を含みます｡したがって、3-1です｡
よって、



つまり、整数の33.3%にまで絞れるのです｡

同じく､30n+Pは、(2x3x5)n+Pですから
整数は、5n、5n+1,5n+2,5n+3,5n+4とも書くことができます｡5nは5の倍数ですから5n+1,5n+2,5n+3,5n+4が素数を含みます｡したがって、5-1です｡
よって、



つまり、整数の26.7%にまで絞れるのです｡

また、210n+P=(2x3x5x7)n+Pでは、同様にして



つまり、整数の22.9%にまで絞れるのです｡

また、2310n+P=(2x3x5x7x11)n+Pでは、同様にして



つまり、整数の20.8%までしぼれるのです｡

さらに、30030n+P=(2x3x5x7x11x13)n+Pでは、同様にして



つまり、整数の19.2%まで絞れます｡

このように、予めエラトステネスの篩をかける数を絞っているので､時間とメモリの節約になるのです｡
intは32ビットのシステムですから、符号をのぞくと２³¹＝21,4748,3648が最大数ですがコンパイラの最大数が21,4748,3647と定義されていますのでこれが最大です｡

いま、210n+Pのばあい、22.9%でしたから､4億9千万個がくらいが限界となります｡
実際は4億8千万個まで確認しています｡


第二節　プログラムの概要

ここでは、auto_sosuu-5.cが基本となるプログラムで､以上の候補の生成式の違いを引き受けるのがinclude_flag_set.cなのです｡
include_flag_set.cは素数表を必要とします｡

そこで、まず300万個の素数を求めた表をダウンロードしてください｡
sosuuhyo.tgz のダウンロード

include_flag_set.tgz のダウンロード

include_flag_set.tgzの中身の説明
漢字コードの違いにより
include_flag_set.sjis.c　　シフトJISコード
include_flag_set.euc.c　 EUCコード
include_flag_set.utf.c　　UTF8コード
３つのCのソースプログラムが入っています｡
処理系の漢字環境で選択して下さい｡
ソースのはじめの行の以下の行を変えることで求める素数候補を指定できます｡

#define nn 48000000

今4億8千万となっていますが、これを書き換えることで素数候補の数を変えることができます｡
1億はメモリ400MB消費しますので5億では2GB以上必要です｡
足りないとスワップが起きてとんでもない時間がかかります｡

もう一つ
#define　prime_table_size　4

も素数候補式に合わせてセットしてください｡

auto_sosuu-5.tgz のダウンロード

auto_sosuu-5.tgzの中身の説明
漢字コードの違いにより
auto_sosuu-5.sjis.c　　シフトJISコード
auto_sosuu-5.euc.c　 EUCコード
auto_sosuu-5.utf.c　　UTF8コード
３つのCのソースプログラムが入っています｡
処理系の漢字環境で選択して下さい｡

素数候補の生成式による違いは、
flag_set.h
init_table.h
del_P_prime.h
に書かれています｡
これは、include_flag_setを実行するとsosuuhyoをもとに生成されます｡


第三節　実行方法

すべて、解凍し、同じディレクトリに,あつめます｡
漢字コードにあわせて、SjisとかEUCとかutfを削ったファイル名にします｡

ここでは､素数候補4億8千万、生成式210n+Pの場合を示します。
メモリは2GB程度使っています｡

$ gcc -Wall include_flag_set.c -o include_flag_set　　　コンパイル
$ ./include_flag_set　　　　　　　　　実行
sosuuhyo read!  3000000 個　　　読みこんだ素数の数
now saving  disk file!
Q個数=48
$ gcc -Wall auto_sosuu-5.c -o auto_sosuu-5
$ ./auto_sosuu-5
init table end!
delete P prime start!
篩=45827 経過時間= 7 分 30 秒
now saving  disk file!
素数個数=102886524　　　　　　　求めた素数の数

実行結果は､sosuuhyoでなくsouuhyoとして出力されます｡
sosuuhyoは消さないでください｡

なお、gccのバージョンは4.1.2で環境はVine　Linux5CRで確認しています｡

なお、210n+pと2310n+Pと30030n+Pとで素数1億個の値は虱潰し法の結果と一致することは確認しています｡



つづく

メインページに戻る