2.9　連續合數集

正整數中，作為整數基本單位的1是形單影只的“孤家寡人”，而素數與合數則是兩個“人丁興旺”的大家族。前一章探討的整數大多是合數，而這一章集中探討素數。

最后探討兩個有趣的連續合數集問題，這兩個問題實際上與素數分布密切相關。

2.9.1　最小連續合數集

首先看一個簡單的連續合數問題及其解答。

【問題】　請寫出10個連續合數區間。

【探求】　試用以下3種方式寫出10個連續合數區間。

（1）利用階乘來寫。

11?。玨（k＝2~11），得10個連續合數區間[39916802，39916811]。

因為11！中有2，3，…，11，因此11?。玨（k＝2，3，…，11）能被k整除，即都是合數。

（2）利用最初幾個素數的乘積來寫。

2×3×5×7×11＋k（k＝2~11），得10個連續合數區間[2312，2321]。

因為乘積2×3×5×7×11包含有5個最小的素數，k為偶數時有2因數，k為奇數時有前面的素數因數，所以2×3×5×7×11＋k（k＝2，3，5，7，11）自然都是合數。

（3）利用相鄰素數中的間距來確定。

首先搜索前30個奇素數備查。

3 5 7 11 13 17 19 23 29 31 37 41 43 47 53

59 61 67 71 73 79 83 89 97 101 103 107 109 113 127

然后從小到大依次求相鄰兩素數之差，若差大于10，即可寫出10個連續合數。

易得113之前的差均小于10，而127-113＝14＞10，則得10個連續合數為[114，123]。

以上探求的3個寫法中，第2個寫法的10個連續合數區間比第1個寫法的10個連續合數要小得多；第3個最小，無疑是最小的10個連續合數集。

進一步，如何求取最小的n個連續合數？

【拓展】　試探求最小的連續n（n≤200）個合數（其中n是鍵盤輸入的任意正整數）。

（1）編程設計要點。

求出區間[c，d]內的所有素數（區間起始數c可由小到大遞增），檢驗其中每相鄰兩素數之差。若某相鄰的兩素數m，f之差大于n，即m-f＞n，則區間[f＋1，f＋n]中的n個數為最小的連續n個合數。

應用試商法求指定區間[c，d]（約定起始數c＝3，d＝c＋10000）上的所有素數。求出該區間內的一個素數m，設前一個素數為f，判別：若m-f＞n，則輸出結果[f＋1，f＋n]后結束；否則，作賦值f＝m，為求下一個素數作準備。

如果在區間[c，d]中沒有滿足條件的解，則賦值c＝d＋2，d＝c＋10000，繼續試商下去，直到找出所要求的解。

（2）程序設計。

（3）程序運行示例與說明。

     求最小的n個連續合數,請輸入n(n≤200):100
     最小的100個連續合數區間為:[370262,370361]。

隨著n的增加，最小的n個連續合數隨之迅速變大，搜索也隨之變得困難。例如，輸入n＝200，搜索最小200個連續合數區間[20831324，20831523]，所用時間就比較長。

2.9.2　一枝花與清一色世紀

一個世紀的100個年號中常存在素數。例如，現在所處的21世紀的100個年號中存在2003，2011等14個素數。

那么，在100個年號中只有一個素數的世紀什么時候出現？是否存在一百個年號中沒有素數的世紀？

【定義】　把一個世紀的100個年號中只有一個素數年號的世紀稱為單素“一枝花”世紀。把世紀的100個年號中不存在素數，即100個年號全為合數的世紀稱為合數“清一色”世紀。

【探求】　試探索最早的m個一枝花世紀與最早的m個清一色世紀。這里正整數m從鍵盤輸入。

1. 編程設計要點

設變量b統計清一色世紀個數，變量c統計一枝花世紀個數。

（1）設置循環。

要兼顧兩項任務，設置條件循環的條件為b＜m||c＜m。

也就是說，當b＝m且c＝m時（已達到目標）才結束循環。

探索a世紀，從a＝1開始遞增1取值。設第a世紀的50個奇數年號（偶數年號無疑均為合數）為n，顯然有a×100-99≤n≤a×100-1。

設置n（a×100-99~a×100-1）循環，n步長為2，枚舉a世紀奇數年號n；

設置k（3~）試商循環，k步長為2，應用試商判別年號n是否為素數：

若n為素數，則用變量x記錄該素數年號；

若n為合數，則用變量s統計這50個n年號中的合數的個數。

（2）判別與輸出。

對于a世紀，若s＝49，即49個奇數都為合數，找到a世紀為一枝花世紀，用＋＋b統計一枝花世紀的個數，并打印輸出第b個一枝花世紀為a世紀，同時輸出其一枝花，即該世紀的唯一素數x。

對于a世紀，若s＝50，即50個奇數都為合數，找到a世紀為清一色世紀，用＋＋c統計清一色世紀的個數，并打印輸出第c個清一色世紀為a世紀，同時輸出其年號范圍。

當b＝m且c＝m時，已搜索到前m個清一色世紀與前m個一枝花世紀，退出循環結束。

2. 程序設計

3. 程序運行示例與分析

     請確定搜索個數m:3
     第1個一枝花世紀為:1560世紀,唯一素數年號為155921。
     第2個一枝花世紀為:2684世紀,唯一素數年號為268343。
     第3個一枝花世紀為:4134世紀,唯一素數年號為413353。
     第1個清一色世紀為:16719世紀,年號[1671801,1671900]全為合數。
     第2個清一色世紀為:26379世紀,年號[2637801,2637900]全為合數。
     第3個清一色世紀為:31174世紀,年號[3117301,3117400]全為合數。

枚舉設計三重循環，要求的m越大，a遞增取值也就越大，年號n也就相應越大。約定最大年號為n數量級，試商k循環頻數為，因而可知程序的時間復雜度為O（n）。

在實際檢測時，對于m≤100范圍內的搜索是快捷的。

由搜索輸出可知，最先出現的一枝花世紀為1560世紀，還要經歷十多萬年，可謂地久天長，遙遙無期！而清一色世紀更為遙遠，最先出現的清一色世紀為16719世紀，還要經歷一百多萬年，更是?？菔癄€，地老天荒！