Scrratch計(jì)算質(zhì)數(shù)

在數(shù)學(xué)王國中，數(shù)學(xué)家根據(jù)不同數(shù)的特性給它們起了不同的名字，有的叫奇數(shù)，有的叫偶數(shù)，還有的叫質(zhì)數(shù)……今天我們就來探討一下這個質(zhì)數(shù)。

質(zhì)數(shù)又稱素?cái)?shù)，一個大于1的自然數(shù)，除了1和它自身外不能被其他自然數(shù)整除的數(shù)叫做質(zhì)數(shù)，否則稱為合數(shù)。質(zhì)數(shù)的個數(shù)是無窮多的，2、3、5、7、11這些都是質(zhì)數(shù)。懂得什么是質(zhì)數(shù)后，我們就會考慮如何做一個程序判斷該數(shù)是不是質(zhì)數(shù)呢？雖然質(zhì)數(shù)是無窮多個，我們能不能計(jì)算出100以內(nèi)的所有質(zhì)數(shù)呢？

已知，質(zhì)數(shù)就是只能被1和它自身兩個數(shù)相除的數(shù)。因此，要判斷一個大于2的自然數(shù)n是不是質(zhì)數(shù)（默認(rèn)2是為質(zhì)數(shù)），最簡單的辦法就是看n能不能被2到n-1中的某個數(shù)整除。只要有一個數(shù)能被n整除，n就是合數(shù);如果都不能整除，n就是質(zhì)數(shù)。比如97，我們就看它能不能被2到96中的某一個數(shù)整除。很顯然97不能被2到96中的數(shù)字給整除，所以97是一個質(zhì)數(shù)。

這個方法雖然簡單粗暴，卻也有很大弱點(diǎn)，就是隨著數(shù)字變大會消耗很長的運(yùn)算時(shí)間。如果數(shù)字非常巨大還用手工計(jì)算當(dāng)然是不可能，而使用計(jì)算機(jī)來計(jì)算卻還是有那么一點(diǎn)希望的，計(jì)算質(zhì)數(shù)也是測試計(jì)算機(jī)運(yùn)算能力的一個常用辦法呢。

好了現(xiàn)在我們先來看看判斷某一個數(shù)字是不是質(zhì)數(shù)的流程圖。

判斷輸入的數(shù)字是否能被i給整除，如果該數(shù)字能被i整除了（余數(shù)=0），那么該數(shù)就不是質(zhì)數(shù)，是合數(shù)，如果不能，則該數(shù)字就是質(zhì)數(shù)。

在此基礎(chǔ)上我們從2開始依次判斷每個數(shù)是不是質(zhì)數(shù)，如果是的話就加入到質(zhì)數(shù)列表里，否則加入合數(shù)列表。還有幾個技巧就是當(dāng)出現(xiàn)整除情況后，怎樣停止本次循環(huán)，我們使用直接賦值n=1完成循環(huán)判斷。然后去判斷下一個自然數(shù)是不是質(zhì)數(shù)。

結(jié)合流程圖和程序代碼，我們一起來讀懂代碼。

總數(shù)是用戶設(shè)定的計(jì)算范圍。

變量n是總數(shù)以內(nèi)的自然數(shù)從2開始，依次遞增。

變量i作為除數(shù)，取值范圍2到n。

變量“是否為質(zhì)數(shù)”用于記錄判斷n是否質(zhì)數(shù)的結(jié)果。初始默認(rèn)這個數(shù)是素?cái)?shù)標(biāo)記為1，如果能被整除那么就改變值為0，即不是質(zhì)數(shù)，停止本次重復(fù)執(zhí)行。

梅森素?cái)?shù)

提前停止本次重復(fù)是一個減少計(jì)算量的小技巧。因?yàn)樾枰貜?fù)執(zhí)行到i=n，一旦遇到可以整除時(shí)就直接修改i的值，使執(zhí)行結(jié)束的條件成立，減少不必要的運(yùn)算量。

每個自然數(shù)n重復(fù)執(zhí)行除法判斷結(jié)束后根據(jù)變量“是否為質(zhì)數(shù)”來確定最終結(jié)果，如果等于1就是質(zhì)數(shù)，添加進(jìn)質(zhì)數(shù)列表，否則加入合數(shù)列表。

小知識：梅森素?cái)?shù)

與質(zhì)數(shù)（素?cái)?shù)）有關(guān)的“互聯(lián)網(wǎng)梅森素?cái)?shù)大搜索（GIMPS）”項(xiàng)目是旨在找到更大的梅森素?cái)?shù)——既是梅森數(shù)（少量素?cái)?shù)可寫成“2的n次方減1”<2^n-1>的形式）又是素?cái)?shù)（質(zhì)數(shù)）的數(shù)。

手工運(yùn)算發(fā)現(xiàn)的最大梅森素?cái)?shù)是1876年數(shù)學(xué)家盧卡斯發(fā)現(xiàn)的2^127-1.這是一個39位的數(shù)。2018年，計(jì)算機(jī)發(fā)現(xiàn)了第51個梅森素?cái)?shù)：2^82589933-1（被稱為M82589933），共有24862048位。