歡迎轉發到朋友圈
質數（也稱素數）是指在大於1的自然數中，除了1和它本身以外不再有其他因數的自然數，否則就稱合數（規定1即不是質數也不是合數）。
自古以來，數學家們就想弄明白：自然數中到底有多少個質數，質數的分布有什麼規律，如何去尋找質數。
公元前300多年，希臘學者埃拉託色尼提出了一種方法，先把自然數列的數寫在一個表中，然後把其中的合數一個一個地挖去。步驟如下:
❶ 先把1刪除；
❷ 讀取數列中當前最小的數2，再把2的倍數刪除；
❸ 讀取數列中當前最小的數3，再把3的倍數刪除；
❹ 依次進行下去，直到把所求範圍內的數均讀取完。
以上就是著名的埃拉託色尼篩選法。
1934年，在埃拉託色尼選去問世兩千多年後，一位年輕的印度學生辛答拉姆創造了如圖所示的一個數表，利用這個數表找質數的方法被稱為「辛答拉姆篩法"。
通過上表可以發現：每一行數都是等差數列。
數表的第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。
那麼，如何讓利用辛答拉姆篩法尋找質數呢，方法如下：
(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列的數，與假設相矛盾，故辛達拉姆篩法成立。
與埃拉託色尼篩法相比，辛達拉姆篩選質數的方法並不是那麼直觀和易操作，但是基於辛達拉姆篩法設計的判斷質數的程序要比常規方法快一倍，在學習中，多了解一種方法，就能讓我們感受到一次數學的魅力所在。
為了方便大家下次查看，請點擊下面「在看」需要的時候可以快速查看這條消息！
來源：本文來源於雲南教育快訊，謹致感謝，如有侵權，請聯繫刪除！
雲南學慧教育校區服務中心:
一校地址：經典雙城校區
昆明市高新區經典名居學慧教育10幢（西山一中斜對面）
二校地址：中天融域校區
中天融域二期（廣福路與前興路交叉口）23幢1單元2層209號
三校地址：潤城校區
潤城四區3幢105室（潤城師大附中對面）
諮詢電話：0871-63133336 0871-63812619
15925165546（楊老師）