森德拉姆篩法
又一個篩。森德拉姆 (Sundaram) 其人不過是東印度 (即現孟加拉國,在未獨立前為印度管治) 的窮苦學生。時 1934 年,他創了一個富有特式的森德拉姆篩法 (Sieve of Sundaram) 了。
方法如下
4 |
7 |
10 |
13 |
16 |
19 |
22 |
25 |
28 |
...... |
7 |
12 |
17 |
22 |
27 |
32 |
37 |
42 |
47 |
...... |
10 |
17 |
24 |
31 |
38 |
45 |
52 |
59 |
66 |
...... |
13 |
22 |
31 |
40 |
49 |
58 |
67 |
76 |
85 |
...... |
16 |
27 |
38 |
49 |
60 |
71 |
82 |
93 |
104 |
...... |
19 |
32 |
45 |
58 |
71 |
84 |
97 |
110 |
123 |
...... |
22 |
37 |
52 |
67 |
82 |
97 |
112 |
127 |
142 |
...... |
25 |
42 |
59 |
76 |
93 |
110 |
127 |
144 |
161 |
...... |
28 |
47 |
66 |
85 |
104 |
123 |
142 |
161 |
180 |
...... |
...... |
...... |
...... |
...... |
...... |
...... |
...... |
...... |
...... |
...... |
建立如上表的森德拉姆對稱矩陣 (Matrix):
矩陣第一行為首項
4,公差 3 的算術數列 (Arithmetic Sequence)。
矩陣第二行為首項
7,公差 5 的算術數列。
矩陣第三行為首項
10,公差 7 的算術數列。
這樣下去,下一行的首項是上一行的
+3 ,而公差則是上一行的 +2。
這矩陣奇妙之處在於:如果一自然數
N 在表中某處出現,則 2N+1 不是素數; N 在表中找不到,則 2N+1 是素數。
不妨看看實例吧:表是從 4 開始,略過了 1、2、3,這 2*1+1=3 、2*2+1=5 和 2*3+1=7 都是素數。
現已證明,這篩子是可信的,不會有反例 (Counterexample)。
原因很簡單,我們不難發現,表中第一行所有數字均屬 3k+1 類,而表中第二行所有數字均屬 5k+2 類,表中第二行所有數字均屬 7k+3 類:如此類推,表中第 n 行的所有數字均屬 (2n+1) * k + n 類別。當然,這些算術級數亦包括所有比 (2n+1) 大的數值。那麼,把屬於第一行的數字乘 2 加 1 以後便是 3 的倍數,把屬於第二行的數字乘 2 加 1 以後便是 5 的倍數,把屬於第三行的數字乘 2 加 1 以後便是 7 的倍數,把第 n 行的數字乘 2 加 1 以後便是 (2n+1) 的倍數。試想像一數不在表中出現是什麼意思,即它的「兩倍添一」是一奇數,但不是任何比它一半少的奇數的倍數:這樣的奇數不是素數才怪。
雖云森德拉姆篩法可信,但使用時不見得比埃拉托斯特尼篩法 (Sieve of Eratosthenes) 方便。而森德拉姆篩法不會把所有素數列出,這和埃拉托斯特尼篩法沒有遺漏的把所有素數找出來不同:例如惟一的偶素數 2 ,在森德拉姆的篩法下便無法找到了。