辛達拉姆篩法

印度學生辛答拉姆創造的數表，這種找質數的方法，被稱為辛答拉姆篩法。

基本介紹

• 中文名：辛達拉姆篩法
• 發明者：埃拉托色尼

基本簡介

1934年，印度學生辛答拉姆創造的數表，這種找質數的方法，被稱為辛答拉姆篩法。

辛答拉姆篩法

（1）如果M在數表中，那么 2M+1 一定不是質數，例如，M=4 在數表中，2M+1=9，9不是質數；M=17 在數表中，2M+1=35，35不是質數。

（2）如果 M 不在數表中，那么 2M+1 一定是質數，例如，M=5 不在數表中，2M+1=11，11是質數，M=8 不在數表中，2M+1=17，17是質數。

證明

（1）假設 M 是數表中第m行第n列的數，則 M=2mn+m+n，於是2M+1=4mn+2m+2n+1=(2m+1)(2n+1)，是合數。

（2）對於 M 不在數表中的情況，想要正面證明 2M+1 是質數相當困難，所以我們考慮用“反證法”。假設 2M+1 不是質數，則 2M+1=xy（x，y為整數），由於 2M+1 為奇數，所以x，y也必為奇數，不妨設 x=2p+1，y=2q+1，從而 2M+1=(2p+1)(2q+1)=4pq+2p+2q+1，故 M=2pq+p+q，根據前面的分析可知 M 是數表中第p行第q列的數，與假設相矛盾，故辛達拉姆篩法成立。

規律

數表的第1行第1列都是首項為4，公差為3的等差數列，這樣第1行第m個數就可以表示為：4+3(m-1)=3m+1。而第1列與第1行的數都相同，所以第m行第1個數也是3m+1。從第2行開始，以後每一行也都是等差數列，公差分別為5，7，9，11，13，……，即2m+1，因此第m行第n個數為3m+1+(2m+1)(n-1)=2mn+m+n。

總論

與埃拉托色尼篩法相比，辛達拉姆篩選質數的方法並不是那么直觀和易操作，不過有研究表明，基於辛達拉姆篩法設計的判斷質數的程式要比常規方法快一倍。