第 34 课：质数和合数
质数和合数在生活中有着比较广泛的应用，氪町博士为了让大家了解它们的应用，举了一些相关的例子。
质数的应用
比如，现代密码学通过两个大质数相乘的方式来加密和解密信息，确保信息在传输和存储过程中的安全性。像银行转账、网上购物等涉及敏感信息传输的场景，都依赖这种基于质数的加密技术来保障用户数据的安全。
在机械制造领域，为了使齿轮的磨损均匀，延长齿轮的使用寿命，制造者通常会将相邻两个齿轮的齿数设计为质数。
合数的应用
包装设计经常会用到合数，因为如果产品数量是合数的话，就可以根据合数的因数分解情况，设计出不同规格的包装方案。比如有 36 个产品，可以设计成 6 × 6、4 × 9、3 × 12 等不同排列方式的包装盒，方便运输、存储和销售。
接下来，我们再跟随氪町博士学习一下质数和合数在编程中有哪些应用。
34.1 质数的概念及判断
质数又称素数，是指只能被 1 和它本身整除的，大于 1 的自然数。换句话说就是有且只有两个因数的正整数就是质数。
以下列出了几个判断是质数还是合数的例子。
6 的因数有 1、2、3、6，除了 1 和 6 之外还多了 2 和 3 两个因数，因此 6 不是质数。
7 的因数有 1、7，有且只有 1 和 7 本身两个因数，所以 7 是质数。
5 的因数有 1、5，有且只有 1 和 5 本身两个因数，所以 5 是质数。
利用"小旗子"判断质数
"小旗子"的作用。 在循环外定义一个变量 flag（小旗子），初始化为 0（代表放下的状态）。在循环中如果满足某个条件，则将 flag 变为 1（即将小旗子举起来），用来表示循环中出现某种情况。
判断质数。 现在我们利用"小旗子"来判断数 a 是不是质数。先将 flag 初始化为 0，在循环中枚举 a 的因数，发现有除了 1 和 a 本身之外的其他因数的情况下将 flag 改为 1，则表示数 a 不是质数。最后只需要看 flag 这面旗子是放下的（0）还是举起来（1）的状态，就可以判断出这个数是不是质数。
例 1：质数判断
任给一个自然数 n（1 ≤ n ≤ 10000），判断 n 是否为质数，如果是则输出 YES，否则输出 NO。
【输入格式】输入一行，一个正整数 n。
【输出格式】输出一行，YES 或者 NO。
【输入样例】121
【输出样例】NO
【样例解释】121 除了 1 和 121 之外还有其他因数，比如 11 也是 121 的因数，所以 121 不是质数，因此输出 NO。
解析
采用枚举法，从 2 开始到该数（假设该数是 a）的前一个数进行遍历，检查是否存在能整除该数的数。如果存在这样的数，那么这个数就不是质数；如果不存在，那么这个数就是质数。
使用 flag 作为标志变量，初始值设为 0，先假设输入的数是质数。如果在后续的检查过程中发现该数有除了 1 和它本身之外的因数，就将 flag 的值设为 1。
使用 for 循环从 2 开始到 a - 1 进行遍历，检查是否存在能整除 a 的数。如果存在这个数则说明 a 除了 1 和它本身之外还有其他因数，因此 a 不是质数。
若满足上述情况，则将标志变量 flag 的值设为 1，表示 a 不是质数。
一旦发现 a 有除了 1 和它本身之外的因数，就可以提前结束循环，因为已经确定 a 不是质数了。
参考代码
#include <iostream>
using namespace std;
int main()
{
int a, flag = 0; // 假设是质数，旗子放下的状态
cin >> a;
for (int i = 2; i < a; i++)
{
if (a % i == 0)
{
flag = 1; // 出现因数，把旗子举起来，说明 a 不是质数
break;
}
}
if (flag == 0) // 判断旗子是否被举起
cout << "YES";
else
cout << "NO";
return 0;
}优化判断质数程序
上面判断质数的程序的时间复杂度为 O(n)，这个时间复杂度可以优化成 O(√n)，它们的效率相差多大呢？
随着输入规模 n（要判断的数的大小）的不断增大，O(√n) 复杂度的算法运行时间的增长速度远慢于 O(n) 复杂度的算法，时间越短，效率越高。例如，当 n = 100 时，√n = 10；当 n = 10000 时，√n = 100。n 从 100 增长到 10000 是 100 倍的增长，√n 仅仅是 10 倍的增长。
若 n 为 10000，时间复杂度为 O(√n) 的程序效率比时间复杂度 O(n) 的程序高出 100 倍，若数字继续增长，效率还将继续提高。那怎么将判断质数的程序优化成 O(√n) 的时间复杂度呢？
在上一节中我们提到过，因数是成对出现的，比如 16 的因数是 1 和 16、2 和 8、4 和 4。这些因数分别从最大和最小向中间靠拢，而这个中间值并不是这个数的一半，而是这个数的算术平方根。
所以只需要从 2 开始判断到这个数字的算术平方根的位置，就可以断定这个数是不是质数了。
例 2：判断质数 2
任给一个自然数 n（1 ≤ n ≤ 100000000000），判断 n 是否为质数，如果是则输出 YES，如果不是则输出除了 n 自身外最大的因数，如果 n 是 1 就输出 1。
【输入格式】输入一行，一个正整数 n。
【输出格式】输出一行，YES，或者除 n 以外的最大因数或者 1。
【输入样例】123
【输出样例】41
解析
质数判断原理：要判断一个数 n 是否为质数，只需检查 2 和 √n 之间是否存在能整除 n 的数。这是因为如果 n 有一个大于 √n 的因数 m，那么必然存在一个小于 √n 的因数 k，使得 m × k = n。例如，若 n = 12，√n ≈ 3.46，我们检查到 2 时，发现 12 / 2 = 6，就知道 12 不是质数了。
因数查找：如果在从 2 到 √n 的检查过程中，找到了一个能整除 n 的数 i，那么 n / i 就是除 n 自身外的一个因数。由于我们是从较小的数开始检查，所以第一次找到的能整除 n 的数 i 是较小的因数，而 n / i 就是除 n 自身外的最大因数。例如，对于 n = 123，当 i = 3 时，123 / 3 = 41，41 就是除 123 自身外的最大因数。
特殊情况处理：当 n = 1 时，它既不是质数也没有除自身外的其他因数，所以直接输出 1。
参考代码
#include <iostream>
#include <cmath>
using namespace std;
int main()
{
long long a, t; // 注意输入的 a 和最大因数 t 的取值范围
int flag = 0;
cin >> a;
for (int i = 2; i <= sqrt(a); i++)
{
if (a % i == 0)
{
flag = 1;
t = a / i;
break;
}
}
if (a == 1) // 判断三种情况，a 等于 1 时
cout << 1;
else if (flag == 0) // a 为质数时
cout << "YES";
else // a 不等于 1 且不为质数时
cout << t;
return 0;
}34.2 合数和质因数
若正整数 a ≠ 0，a ≠ 1，且 a 不是质数，则 a 为合数。
若一个质数 a 是另一个数 b 的因数，那么就说这个质数 a 是这个数 b 的质因数。例如对于整数 8，8 的因数有 1、2、4、8，其中 2 是质数，所以 2 是 8 的质因数。
例 3：寻找质因数
如果一个质数 a 是另一个数 b 的因数，那么就说这个质数 a 是这个数 b 的质因数。任给一个自然数 a（2 ≤ a ≤ 10000），找出它的质因数，并从小到大进行输出。
【输入格式】输入一行，一个正整数 a。
【输出格式】输出一行，包含 a 的所有质因数，以空格隔开。
【输入样例】180
【输出样例】2 3 5
解析
目标是找出给定自然数 a（2 ≤ a ≤ 10000）的所有质因数，并将这些质因数从小到大进行输出。已知质因数是指既是质数，又能整除给定数 a 的因数。
判断是否为因数：从 2 开始，依次遍历到 a，对于每个数 i 进行检查，检查 i 是否能整除 a，即判断 a 除以 i 的余数是否为 0。如果余数为 0，说明 i 是 a 的一个因数。
判断是否为质数：对于确定为因数的 i，需要进一步判断它是否为质数。为了判断 i 是否为质数，我们可以从 2 开始，检查到 √i。如果在这个范围内存在能整除 i 的数，那么 i 就不是质数，否则 i 是质数。
输出质因数：如果 i 既是 a 的因数，又是质数，那么 i 就是 a 的一个质因数，将其输出。
去除重复质因数：为了避免重复输出相同的质因数，当找到一个质因数 i 后，将 a 中所有 i 的倍数去除，即不断将 a 除以 i，直到 a 不能再被 i 整除为止。
参考代码
#include <iostream>
#include <cmath>
using namespace std;
int main()
{
int a;
cin >> a;
for (int i = 2; i <= a; i++)
{
int flag = 0;
if (a % i == 0) // 判断因数
{
for (int j = 2; j <= sqrt(i); j++)
{
if (i % j == 0)
{
flag = 1;
break;
}
} // 判断质数
if (flag == 0)
cout << i << " ";
while (a % i == 0)
a /= i; // 去重步骤
}
}
return 0;
}34.3 埃拉托色尼筛法
如果一个数 a 是合数，那么肯定能找到一个质数 p，这个质数 p 能够整除 a，并且这个质数 p 小于或等于 √a。
上面的描述给出了一个寻找一定范围内所有质数的算法，例如求 100 以内的所有质数的算法。
只需要将不超过 10（√100）的全部质数（2、3、5、7）找出，然后删去它们在 100 以内的所有倍数，就删去了所有 100 以内的合数，剩下的就是 100 以内的质数。
从上面的方法出发，还能寻找 10000（100 的算术平方根）以内的所有质数，这种寻找质数的方法称为埃拉托色尼筛法，简称埃氏筛。
埃氏筛是一种用于寻找质数的算法，它利用了所有比当前数字小的质数，将非质数筛选掉。具体过程如下。
首先，创建一个长度为 n + 1 的布尔类型数组，设置初始值都为 true，即先假设所有的数均为质数。
从 2 开始依次遍历到 √n，将每个质数 p 的倍数标记为非质数，即在数组中将 p 的倍数下标对应的值设置为 false。
遍历数组，将值为 true 的下标对应的数字输出，即为质数列表。
筛出不超过 36 的所有质数
根据上面步骤，我们筛出不超过 36 的所有质数。
- 首先创建一个布尔类型的数组 primes，将其初值全部设为 true，用来标记当前下标对应的数字是否为质数，即先假设 0~36 都是质数。代码如下：
bool primes[37];
for (int i = 0; i <= 36; i++) {
primes[i] = true;
}- 将 primes[0] 和 primes[1] 设为 false，因为 0 和 1 明显不是质数。
primes[0] = primes[1] = false;- 从 2 开始遍历到 6，即遍历到 √36，将每个质数 p 的倍数标记为 false，即在 primes 数组中将 p 的倍数下标对应的值设置为 false。
for (int p = 2; p <= 6; p++)
{
if (primes[p]) // 如果 p 是质数（一开始假设所有数都是质数）
{
for (int i = 2; i * p <= 36; i++)
primes[i * p] = false; // 将 36 以内的 p 的倍数全部标记为合数
}
}- 遍历数组，输出所有值为 true 的下标对应的数字，即质数列表。
for (int i = 0; i <= 36; i++)
{
if (primes[i])
cout << i << " ";
}参考代码
#include <iostream>
#include <cmath>
using namespace std;
int main()
{
int n;
cin >> n;
bool primes[n + 1];
for (int i = 0; i <= n; i++)
primes[i] = true; // 先假设所有的数都是质数
primes[0] = primes[1] = false; // 0 和 1 不是质数
for (int i = 2; i * i <= n; i++)
{
if (primes[i])
{
for (int j = i * i; j <= n; j += i) // 删去质数 i 在 n 以内的倍数
primes[j] = false;
}
}
for (int i = 0; i <= n; i++)
{
if (primes[i])
{
cout << i << " "; // 若未被删去，则说明 i 是质数，输出 i
}
}
return 0;
}