素数探索

PHP

予め生成しておいたテーブルから素数を探索するクラスを作ってみました。
31ビットで表せる素数は 2 から 2147483647 (0x7fffffff も素数!) までの約1億500万個あるのですが、二分探索法を使って高速・省メモリに素数を調べることができます。

ダウンロード

容量と転送量の都合で素数テーブルは65535個に切り詰めています。

テーブルの生成には数時間 (時間を計測せずに放置していたので正確な時間は不明) かかり、最終的に約400MB のメモリとディスク容量が必要でした。
Core2 クラスの CPU なら、進捗状況の表示をせず、一括で malloc(sizeof(uint32_t) * nprimes) すれば1時間程度で終わりそうな印象です。

使用例

<?php
require_once 'Math_Prime.php';

$p = new Math_Prime('pn_le.dat');

echo "Prime Number Table Information:?n";
printf("All: %d?n", $p->count());
printf("1st: %d?n", $p->getPrime(1));
printf("Max: %d?n", $p->getPrime($p->count()));
printf("Chk: %d?n", $p->isPrime($p->getPrime($p->count())) == $p->count());
echo "?n";

echo "Check for 1 to 20:?n";
for ($i = 1; $i <= 20; $i++) {
    printf("%d -> %d?n", $i, $p->isPrime($i));
}
echo "?n";

出力

Prime Number Table Information:
All: 105097565
1st: 2
Max: 2147483647
Chk: 1

Check for 1 to 20:
1 -> 0
2 -> 1
3 -> 2
4 -> 0
5 -> 3
6 -> 0
7 -> 4
8 -> 0
9 -> 0
10 -> 0
11 -> 5
12 -> 0
13 -> 6
14 -> 0
15 -> 0
16 -> 0
17 -> 7
18 -> 0
19 -> 8
20 -> 0