質數又稱素數。一個大於1的自然數，除了1和它自身外，不能被其他自然數整除的數叫做質數；否則稱為合數。按照規定，1不算素數，最小的素數是2，其後依次是3、5、7、11等等。
早在2500年前，古希臘數學家歐幾裡德就證明了素數是無限的，並提出少量素數可寫成 「2的n次方減1(2^n－1)」 的形式，這裡n也是一個素數。
但是目前人類已知的素數很有限，因為數字越大，要發現新的素數就越困難。不過，很多數學家曾對素數問題進行過研究。17世紀的法國教士馬丁·梅森就是其中成果較為卓著的一位，因此後人將 「2的n次方減1(2^n－1)」 形式的素數稱為梅森素數。隨後，以梅森素數的形式，最大素數的記錄被不斷刷新。
1876年，數學家盧卡斯證明了 2^127－1 是當時已知的最大素數。這個記錄保持了75年，這是一個39位的數。直到1951年，藉助於新出現的電子計算機，人們才發現有79位數字的更大素數。
1952年時，最大素數是 2^2281－1，有687位數。位數在1000位以上的素數到1961年才被發現，它是 2^4423－1，共有1332位數。從1951年到1971年的20年間，最大素數的紀錄被不斷刷新。
1971年，美國數學家塔克曼在紐約州的紐克頓利用 IBM360/91 型電子計算機，歷時39分26.4秒，算出了當時的最大素數 2^19937－1，這是一個6002位的數字，它最前面的五位數是 43154，最後面的三位數是 471。
1978年10月，世界幾乎所有的大新聞機構（包括中國的新華社）都報導了以下消息：兩名年僅18歲的美國高中生諾爾和尼科爾使用CYBER174型計算機找到了第25個梅森素數：M21701。
2008年8月，美國加州大學洛杉磯分校(UCLA)的計算機專家史密斯（E.Smith）通過參加了一個名為「網際網路梅森素數大搜索」(GIMPS)的國際合作項目，發現了第46個也是當時最大的梅森素數 2^43112609-1，該素數也就是 2 自身相乘43112609次減1，它有 12978189 位數，如果用普通字號將這個巨數連續寫下來，它的長度可超過50公裡！這一成就被美國的《時代》雜誌評為「2008年度50項最佳發明」之一，排名在第29位。
據英國《新科學家》雜誌網站報導，美國中央密蘇裡大學數學教授柯蒂斯·庫珀(Curtis Cooper)領導的研究小組於2013年1月25日發現了已知的最大梅森素數——2^57885161-1 (即2的57885161次方減1)；該素數有17425170位，如果用普通字號將它連續列印下來，它的長度可超過65公裡！
另據外媒報導，美國州立中密蘇裡大學柯蒂斯庫珀（Curtis Cooper）通過GIMPS項目發現了第49個梅森素數 2^74207281-1（被稱為M74207281），為GIMPS項目誕生20周年獻禮。
2017年12月26日，網際網路梅森素數大搜索（GIMPS）項目宣布發現第 50 個梅森素數和已知最大的素數：2^77,232,917-1，共有 23,249,425 位。該素數已被多人使用不同的硬體和軟體完成驗證。發現者是 GIMPS 志願者 Jonathan Pace，他住在田納西州的 Germantown，是一位電機工程師，他有資格獲得 3000 美元的研究發現獎。
GIMPS 是一個分布式計算項目，至今已有 20 年歷史，它利用志願者的空閒 CPU 創建了一個遍布全球的超級計算機，它的 prime95 軟體此前發現了英特爾處理器的一個漏洞。
2013年5月，張益唐在孿生素數研究方面所取得的突破性進展，他證明了孿生素數猜想的一個弱化形式。張益唐在不依賴未經證明推論的前提下，發現存在無窮多差小於7000萬的素數對，從而在孿生素數猜想這個重要問題的道路上前進了一大步。
如何判斷一個正整數是否為質數？
以下介紹三種判別質數的方法，並附上相應的Python程序，供有興趣的同學參考。
1）直觀判斷法
最直觀的方法，根據定義，因為質數除了1和本身之外沒有其他因數，所以判斷n是否為質數，根據定義直接判斷從2到n-1是否存在n的因數即可。
2）直觀判斷法改進
上述判斷方法，明顯存在效率極低的問題。對於每個數n，其實並不需要從2判斷到n-1，我們知道，一個數若可以進行因數分解，那麼分解時得到的兩個數一定是一個小於等於sqrt(n)，一個大於等於sqrt(n)，據此，上述代碼中並不需要遍歷到n-1，遍歷到sqrt(n)即可，因為若sqrt(n)左側找不到因數，那麼右側也一定找不到因數。
3）質數規律判斷法
首先看一個關於質數分布的規律：大於等於5的質數一定和6的倍數相鄰。例如5和7，11和13,17和19等等。
證明：令x≥1，將大於等於5的自然數表示如下：
······6x-2，6x-1，6x，6x+1，6x+2，6x+3，6x+4，6x+5，6x+6，6x+7······
也就是
······2(3x-1)，6x-1，6x，6x+1，2(3x+1)，3(2x+1)，2(3x+2)，6x+5，6(x+1)，6(x+1)+1······
可以看到，不在6的倍數兩側，即6x兩側的數為6x+2，6x+3，6x+4，由於2(3x+1)，3(2x+1)，2(3x+2)，所以它們一定不是素數，再除去6x本身，顯然，素數要出現只可能出現在6x的相鄰兩側。這裡要注意的一點是，在6的倍數相鄰兩側並不是一定就是質數。
根據以上規律，判斷質數可以6個為單元快進，即將方法（2）循環中i++步長加大為6，加快判斷速度，代碼如下：
*本文由父子課堂根據csdn及其他網絡內容整理
*轉載請註明父與子的數學和編程課堂（id：mathcoding）
父子課堂由多位北美博士/博士後組成核心團隊，專注於兒童和青少年的編程和數學教育，專業提供Scratch、Python、EV3機器人以及信奧和奧數競賽等內容的培訓課程。歡迎加入父子課堂，在培訓課程之外，還可通過公眾號和交流社群，獲取更多免費學習資源。
父子課堂的願景和宗旨：
讓更多孩子享有更優質的教育資源
加入父子課堂公眾號並把本文發朋友圈，可免費獲贈《父與子的編程之旅：與小卡特一起學Python》電子書。
對本書的讚譽
「這本書將編程變得和煎培根一樣容易。」
——Elisabet Gordon，Eagle Harbor 中學 10 年級學生
「對任何人來說，這都是一本非常出色的 Python 入門書。它非常有趣！」
——Mason Jenkins，Myron B. Thompson Academy7 年級學生
「上到 88 歲，下到 8 歲，任何想學習編程的人都可以閱讀這本書。它不僅以一種有趣的方式介紹了 Python 編程，而且其中的最佳實踐還適用於其他程式語言的學習。」
——Ben Ooms，Sogeti 公司軟體工程師
「如果你想學習編程，或者想教孩子編程，那麼這本書就是你的不二選擇。」
——Cuberick.com
「不論老幼，只要想學習編程這門必備而有趣的技能，這都是一本非常好的介紹性圖書。」
——Sue Gee，www.i-programmer.info 網站
「Warren 和 Carter 由簡入難，直到教會讀者製作有趣的2D圖形遊戲和模擬器。Python 是我向編程新手推薦的首選語言，而本書正是非常好的學習資源。第 1 版出版後，我就一直向學生們推薦它。」
——Dave Briccetti，Dave Briccetti Software LLC 公司軟體開發者和教師
如有侵權請聯繫刪除
更多精彩內容請關注：父與子的數學和編程課堂
長按可識別圖中二維碼
輕鬆關注父與子的數學和編程課堂