第2章 素数世家风采

质数又称素数。一个大于1的自然数，除了1和它自身外，不能被其他自然数整除的数叫做质数；否则称为合数（规定1既不是质数也不是合数）。

质数的个数是无穷的。前10个素数为2, 3, 5, 7, 11, 13, 17, 19, 23, 29，其中2为唯一的偶素数。1既不是素数，也不是合数。

(资料图片)

素数搜索

搜索素数的常用方法：

试商判别法：判别奇数k是否是素数，只要逐一用奇数j（取3, 5, …, sqrt（k））去试商，若上述范围内的所有奇数j都不能整除k，则k为素数。

厄拉多塞筛法：给定一个数 n，从 2 开始依次将 sqrt(n)以内的素数的倍数标记为合数，标记完成后，剩余未被标记的数为素数（从 2 开始）。如此可省去检查每个数的步骤，使筛选素数的过程更加简单。

【编程题】

求指定n位所有素数。

梅森尼数与费马数

梅森尼数是指形如2^n－1的正整数，其中指数n是素数，常记为Mn 。若其是素数，则称为梅森尼素数。

【编程题】

试求出指数n<50的所有梅森尼素数。

有趣的对称素数

对称素数：一个整数m的逆序数就是m本身，则称m为对称数，一个整数m如果是对称数又是素数，则称m为对称素数；例如101，131，929等都是3位对称素数，表现为左右对称，也称为回文素数。

【编程题】

试统计指定n（2< n <10）位对称素数的个数，并输出其中最大的对称素数；

素数的变形金刚

金蝉素数：由1，3，5，7，9 这5 个奇数字排列组成的5 位素数，且同时去掉它的最高位与最低位数字后的三位数还是素数，同时去掉它的高二位与低二位数字后的一位数还是素数。因此，称这些神秘的素数称为金蝉素数。

【编程题】

搜索5位金蝉素数。

超级素数：一个素数，依次从最高位去掉一位，两位……若得到的都是素数，且各数字不为0，则称为超级素数。如137就是超级素数。

【编程题】

输入整数m (1< m <17)，统计m位超级素数的个数，并输出其中最大的超级素数。

素数对

相差为2的两个素数称为孪生素数对，简称孪生素数。如3和5是一对孪生素数，41和43是一对孪生素数。

【编程题】

探索指定区间上的孪生素数对。

如果逆序数对的两个整数都是素数，则称为逆序素数对（或称为回文素数对），如13和31是一对逆序素数对。

【编程题】

探索指定区间上的逆序素数对。

素数表达式

哥德巴赫猜想：任何大于2的偶数都是两个素数之和。

【编程题】

设计程序验证指定区间间中哥德巴赫猜想是否成立，如果区间中的偶数能分解为两个素数之和，则输出该分解和式；如果区间中的某一个偶数不能分解为两个素数之和，则输出反例，推翻哥德巴赫猜想。

欧拉表达式：当x=0, 1, ... , 40时，表达式x^2 - x + 41的值都是素数

勒让德表达式：当x=0, 1, ... , 28时，表达式2x^2 + 29的值都是素数

【编程题】

设计程序验证素数表达式。

试在一定整数范围内枚举a，b，c的值（系数b可为负整数，也可以为0），应用试商判别法，探求二次三项式y = ax^2 +bx + c型的素数表达式。

素数等差数列

素数等差数列，如3，5，7组成3项等差数列；5，11，17，23，29组成一个公差为6的等差数列。

【编程题】

在指定区间[x,y]中如果存在成等差数列的n（n>2）个素数，试求n的最大值，并输出一个最多项数的素数等差数列。

素集“乌兰现象”

把整数按照一定规定排列，其中素数具有挤成一条直线的特性，这种现象称为“乌兰现象”（1963年，数学家乌兰发现）

【编程题】

设计程序，把整数序列1，2，3，4，...，nxn排列成n圈的方螺线数阵，1置放在中心位置，以后各整数依次按逆时针方螺线位置排列。（素数用括号标注）

回旋层叠方阵，从原点（0，0）到（0，1）然后到（1，1）→（1，0）→（2，0）→（2，1）→（2，2）→（1，2）→（0，2）…，行进路线上的每个点有一个整数m，坐标原点时m=0，以后每一步递增1.

【编程题】

设计程序，试构建n阶回旋层叠方阵。用括号标注方阵中的素数。

连续合数集

【编程题】

试探求最小的连续n（n≤200）个合数。

试探求最早的m个一枝花世纪（一个世纪的100个年号中只有一个素数）与最早的m个清一色世纪（一个世纪的100个年号中不存在素数）。

【读者体会】

这一章介绍了一些神奇的素数。

如果需要编程找到这些神奇的素数。

编程设计要点。枚举法、递推法。

1）枚举。计算并确定数据取值范围，然后循环依次处理（可以利用数的一些特征，减小搜索区间，减少运行时间）

2）试商。依据定义，判定是否是素数（试商判别法）

3）判别和统计。依据定义判定。（可以用数组记录中间结果，减小重复计算）