第2章 素數(shù)世家風采

?

質(zhì)數(shù)又稱素數(shù)。一個大于1的自然數(shù)，除了1和它自身外，不能被其他自然數(shù)整除的數(shù)叫做質(zhì)數(shù)；否則稱為合數(shù)（規(guī)定1既不是質(zhì)數(shù)也不是合數(shù)）。

質(zhì)數(shù)的個數(shù)是無窮的。前10個素數(shù)為2, 3, 5, 7, 11, 13, 17, 19, 23, 29，其中2為唯一的偶素數(shù)。1既不是素數(shù)，也不是合數(shù)。

?

2.1 素數(shù)搜索

搜索素數(shù)的常用方法：

試商判別法：判別奇數(shù)k是否是素數(shù)，只要逐一用奇數(shù)j（取3, 5, …, sqrt（k））去試商，若上述范圍內(nèi)的所有奇數(shù)j都不能整除k，則k為素數(shù)。

?

厄拉多塞篩法：給定一個數(shù) n，從 2 開始依次將 sqrt(n)以內(nèi)的素數(shù)的倍數(shù)標記為合數(shù)，標記完成后，剩余未被標記的數(shù)為素數(shù)（從 2 開始）。如此可省去檢查每個數(shù)的步驟，使篩選素數(shù)的過程更加簡單。

?

【編程題】

求指定n位所有素數(shù)。

?

2.2 梅森尼數(shù)與費馬數(shù)

?

梅森尼數(shù)是指形如2^n－1的正整數(shù)，其中指數(shù)n是素數(shù)，常記為Mn?。若其是素數(shù)，則稱為梅森尼素數(shù)。

?

?

【編程題】

試求出指數(shù)n<50的所有梅森尼素數(shù)。

?

2.3 有趣的對稱素數(shù)

對稱素數(shù)：一個整數(shù)m的逆序數(shù)就是m本身，則稱m為對稱數(shù)，一個整數(shù)m如果是對稱數(shù)又是素數(shù)，則稱m為對稱素數(shù)；例如101，131，929等都是3位對稱素數(shù)，表現(xiàn)為左右對稱，也稱為回文素數(shù)。

?

【編程題】

試統(tǒng)計指定n（2< n <10）位對稱素數(shù)的個數(shù)，并輸出其中最大的對稱素數(shù)；

?

2.4 素數(shù)的變形金剛

金蟬素數(shù)：由1，3，5，7，9 這5 個奇數(shù)字排列組成的5 位素數(shù)，且同時去掉它的最高位與最低位數(shù)字后的三位數(shù)還是素數(shù)，同時去掉它的高二位與低二位數(shù)字后的一位數(shù)還是素數(shù)。因此，稱這些神秘的素數(shù)稱為金蟬素數(shù)。

?

【編程題】

搜索5位金蟬素數(shù)。

?

超級素數(shù)：一個素數(shù)，依次從最高位去掉一位，兩位……若得到的都是素數(shù)，且各數(shù)字不為0，則稱為超級素數(shù)。如137就是超級素數(shù)。

?

【編程題】

輸入整數(shù)m (1< m <17)，統(tǒng)計m位超級素數(shù)的個數(shù)，并輸出其中最大的超級素數(shù)。

?

2.5 素數(shù)對

?

相差為2的兩個素數(shù)稱為孿生素數(shù)對，簡稱孿生素數(shù)。如3和5是一對孿生素數(shù)，41和43是一對孿生素數(shù)。

【編程題】

探索指定區(qū)間上的孿生素數(shù)對。

?

如果逆序數(shù)對的兩個整數(shù)都是素數(shù)，則稱為逆序素數(shù)對（或稱為回文素數(shù)對），如13和31是一對逆序素數(shù)對。

【編程題】

探索指定區(qū)間上的逆序素數(shù)對。

?

2.6 素數(shù)表達式

?

哥德巴赫猜想：任何大于2的偶數(shù)都是兩個素數(shù)之和。

【編程題】

設(shè)計程序驗證指定區(qū)間間中哥德巴赫猜想是否成立，如果區(qū)間中的偶數(shù)能分解為兩個素數(shù)之和，則輸出該分解和式；如果區(qū)間中的某一個偶數(shù)不能分解為兩個素數(shù)之和，則輸出反例，推翻哥德巴赫猜想。

?

歐拉表達式：當x=0, 1, ... , 40時，表達式x^2 - x + 41的值都是素數(shù)

勒讓德表達式：當x=0, 1, ... , 28時，表達式2x^2 + 29的值都是素數(shù)

【編程題】

設(shè)計程序驗證素數(shù)表達式。

試在一定整數(shù)范圍內(nèi)枚舉a，b，c的值（系數(shù)b可為負整數(shù)，也可以為0），應用試商判別法，探求二次三項式y(tǒng) = ax^2 +bx + c型的素數(shù)表達式。

?

2.7 素數(shù)等差數(shù)列

?

素數(shù)等差數(shù)列，如3，5，7組成3項等差數(shù)列；5，11，17，23，29組成一個公差為6的等差數(shù)列。

?

【編程題】

在指定區(qū)間[x,y]中如果存在成等差數(shù)列的n（n>2）個素數(shù)，試求n的最大值，并輸出一個最多項數(shù)的素數(shù)等差數(shù)列。

?

2.8 素集“烏蘭現(xiàn)象”

?

把整數(shù)按照一定規(guī)定排列，其中素數(shù)具有擠成一條直線的特性，這種現(xiàn)象稱為“烏蘭現(xiàn)象”（1963年，數(shù)學家烏蘭發(fā)現(xiàn)）

【編程題】

設(shè)計程序，把整數(shù)序列1，2，3，4，...，nxn排列成n圈的方螺線數(shù)陣，1置放在中心位置，以后各整數(shù)依次按逆時針方螺線位置排列。（素數(shù)用括號標注）

?

回旋層疊方陣，從原點（0，0）到（0，1）然后到（1，1）→（1，0）→（2，0）→（2，1）→（2，2）→（1，2）→（0，2）…，行進路線上的每個點有一個整數(shù)m，坐標原點時m=0，以后每一步遞增1.

【編程題】

設(shè)計程序，試構(gòu)建n階回旋層疊方陣。用括號標注方陣中的素數(shù)。

?

2.9 連續(xù)合數(shù)集

?

【編程題】

試探求最小的連續(xù)n（n≤200）個合數(shù)。

試探求最早的m個一枝花世紀（一個世紀的100個年號中只有一個素數(shù)）與最早的m個清一色世紀（一個世紀的100個年號中不存在素數(shù)）。

?

?

【讀者體會】

這一章介紹了一些神奇的素數(shù)。

如果需要編程找到這些神奇的素數(shù)。

編程設(shè)計要點。枚舉法、遞推法。

1）枚舉。計算并確定數(shù)據(jù)取值范圍，然后循環(huán)依次處理（可以利用數(shù)的一些特征，減小搜索區(qū)間，減少運行時間）

2）試商。依據(jù)定義，判定是否是素數(shù)（試商判別法）

3）判別和統(tǒng)計。依據(jù)定義判定。（可以用數(shù)組記錄中間結(jié)果，減小重復計算）

?