2.9　连续合数集

正整数中，作为整数基本单位的1是形单影只的“孤家寡人”，而素数与合数则是两个“人丁兴旺”的大家族。前一章探讨的整数大多是合数，而这一章集中探讨素数。

最后探讨两个有趣的连续合数集问题，这两个问题实际上与素数分布密切相关。

2.9.1　最小连续合数集

首先看一个简单的连续合数问题及其解答。

【问题】　请写出10个连续合数区间。

【探求】　试用以下3种方式写出10个连续合数区间。

（1）利用阶乘来写。

11！＋k（k＝2~11），得10个连续合数区间[39916802，39916811]。

因为11！中有2，3，…，11，因此11！＋k（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世纪，还要经历一百多万年，更是海枯石烂，地老天荒！