post on 04 Mar 2025 about 3160words require 11min
CC BY 4.0 （除特别声明或转载文章外）
如果这篇博客帮助到你，可以请我喝一杯咖啡~
参考博客 判断一个数是不是质数(素数)，3 种方式介绍_判断一个数是否为素数-CSDN 博客 C-CrashCourse/content/c-notes/你不知道的几种素数判断方法，由浅入深，详解.md at master · hairrrrr/C-CrashCourse
根据素数的定义思考。素数是大于 1 的自然数，除了 1 和自身外，其他数都不是它的因子。 那我们就可以用一个循环，从 2 开始遍历到这个数减去 1，如果这个数都不能被整除，那么这个数就是素数。 也就是说： 给定一个数 n , i 从 2 开始取值，直到 n - 1(取整数),如果 n % i != 0 , n 就是素数 进一步思考，有必要遍历到 n - 1 吗？ 除了 1 以外，任何合数最小的因子就是 2，那最大的因子就是 n/2 那我们就遍历到 n/2 就足够了
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
int isPrime(int target) {
int i = 0;
if (target <= 1) {
printf("illegal input!\n");//素数定义
return -1;
}
for (i = 2; i <= target / 2; i++) {
if (target % i == 0)
return 0;//不是素数直接返回0
}
return 1;//是素数返回1
}
在上面的基础上，其实不需要遍历到 $\frac{n}{2}$，只需要到 $\sqrt{n}$（包含 $\sqrt{n}$） 就可以了。
- 为什么只需要检查到 $\sqrt{n}$？
- 因数成对出现：
- 如果 n 不是质数，那么它可以分解为两个因数的乘积，即 n=a×b。
- 假设 a≤b，那么一定有 a≤n 且 b≥n。
- 因此，如果 n 有大于 n 的因数 b，那么它必然有一个小于或等于 n 的因数 a。
- 只需检查较小的因数：
- 如果 n 能被某个数 i 整除（即 n%i==0），那么 i 就是 n 的一个因数。
- 根据上述性质，如果 n 有大于 n 的因数，那么它必然已经被小于或等于 n 的因数检查过了。
- 举例说明：
- 假设 n=36， $\sqrt{36}$=6。
- 检查 2 到 6 的整数：
- 2 是 36 的因数（36%2==0），因此 36 不是质数。
- 如果继续检查 4 和 6，会发现它们也是 36 的因数，但已经不需要了，因为 2 已经证明了 36 不是质数。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
int isPrime(int target) {
int i = 0;
if (target <= 1) {
printf("illegal input!\n");//素数定义
return -1;
}
for (i = 2; i <= (int)sqrt(target); i++) {
if (target % i == 0)
return 0;
}
return 1;
}
从第二种方法开始，我们都是先完成判断素数数组，然后用二分法去查找判断数组 这里说一下以下三种方法牵扯的概念：
- 范围：1 ~ 范围上限 N
- 范围上限 N：判断素数需要用户输入随机素数，这个随机素数的范围是 1 ~ N
- 判断素数数组：将数组的
下标与1 ~ N的自然数一一对应起来。 判断 1 到 N 的自然数是否为素数，其实就是判断数组的下标是否为素数，如果是 给这个下标所对应的判断素数数组元素赋 1，否则赋 0 比如：我要判断 3 是否为素数，我们就找到判断素数数组isPrime中的下标为 3 的元素，即：isPrime[3]如果3是素数 ， 赋值 1，即isPrime[3] = 1如果 3 不是素数，赋值0 ，即isPrime[3] = 0这样我们在用二分法查找时，查找数组下标就可以，找到下标后返回下标对应的判断素数数组的值。 如果是 1 说明下标对应的自然数是素数，否则不是- 思路:如果一个数不能整除比它小的任何素数，那么这个数就是素数 这种“打印”素数表的方法效率很低，不推荐使用，可以学习思想
1
2
3
4
5
6
7
8
9
10
11
12
13
//target：输入的要查找的数
//count：当前已知的素数个数
//PrimeArray：存放素数的数组
int isPrime(int target, int count, int* PrimeArray) {
int i = 0;
for (i = 0; i < count; i++) {
if (target % PrimeArray[i] == 0)
return 0;
}
return 1;
}
思路:
- 我们的想法是，创建一个比范围上限大 1 的数组，我们只关注下标为 1 ~ N（要求的上限） 的数组元素与数组下标（一一对应）。
- 将数组初始化为 1。然后用 for 循环，遍历范围为： $[2,\sqrt{N}]$。如果数组元素为 1，则说明这个数组元素的下标所对应的数是素数。
- 随后我们将这个下标（除 1 以外）的整数倍所对应的数组元素全部置为 0，也就是判断其为非素数。 这样，我们就知道了范围内（1 ~ 范围上限 N）所有数是素数（下标对应的数组元素值为 1）或不是素数（下标对应的数组元素值为 0）
- 用百度百科对埃拉托斯特尼筛法简单描述：要得到自然数 n 以内的全部素数，必须把不大于 的所有素数的倍数剔除，剩下的就是素数。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
// 判断素数的数组 范围上限N
void Eratprime(int* isprime, int upper_board) {
int i = 0;
int j = 0;
//初始化isprime
for (i = 2; i <= upper_board; i++)
isprime[i] = 1;
for (i = 2; i < (int)sqrt(upper_board); i++) {
if (isprime[i]) {
isprime[i] = 1;
}
for (j = 2; i * j <= upper_board; j++) {//素数的n倍（n >= 2）不是素数
isprime[i * j] = 0;
}
}
}
思路: 我们再思考一下上面的埃拉托斯特尼筛法，会发现，在“剔除“非素数时，有些合数会重复赋值。这样就会增加复杂度，降低效率。 比如：范围上限 N = 16 时
- 2 是素数，剔除”2 的倍数“，它们是：4，6， 8，10， 12， 14， 16
- 3 是素数，剔除”3 的倍数”，它们是，6，9，12，15 6，12 是重复的。如何减少重复呢？
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
void PrimeList(int* Prime, bool* isPrime, int n) {
int i = 0;
int j = 0;
int count = 0;
if (isPrime != NULL) {//确保isPrime不是空指针
//将isPrime数组初始化为 1
for (i = 2; i <= N; i++) {
isPrime[i] = true;
}
}
if (isPrime != NULL && Prime != NULL) {
//从2遍历到范围上限N
for (i = 2; i <= N; i++) {
if (isPrime[i])//如果下标（下标对应着1 ~ 范围上限N）对应的isPrime值没有被置为false，说明这个数是素数，将下标放入素数数组
Prime[count++] = i;
//循环控制表达式的意义：j小于等于素数数组的个数 或 素数数组中的每一个素数与 i 的积小于范围上限N
for (j = 0; (j < count) && (Prime[j] * (long long)i) <= N; j++)//将i强制转换是因为vs上有warning，要求转换为宽类型防止算术溢出。数据上不产生影响
{
isPrime[i * Prime[j]] = false;//每一个素数的 i 倍（i >= 2）都不是素数，置为false
//这个是欧拉筛法的核心，它可以减少非素数置false的重复率
//意义是将每一个合数（非素数）拆成 2（最小因数）与最大因数 的乘积
if (i % Prime[j] == 0)
break;
}
}
}
}
Related posts