导语:
本篇博客中含有大量的C语言基础知识及算法,算法有两类:「试商判别法」和「厄拉多塞筛法」
目录
导语:
什么是素数
素数求解的 N 种境界
依次遍历
排半法
开平方
排除偶数
试商判别法(终极版)
厄拉多塞筛法
我们可以通过C语言实现一个简单的数学功能:判断一个数是否为「素数」
在我们要实现素数的判断之前,我们先对素数加以了解:
长文警告
什么是素数
素数是上帝用来描写宇宙的文字(伽利略语)
素数,又称为质数,是不能被 1 与其本身以外的其他整数整除的整数。如 2、 3、 5、 7、 11、 13、 17 是前几个素数,其中 2 为唯一的偶素数。
与此相对应,一个整数如果能被除 1 与其本身以外的整数整除,该整数称为合数或复合数。例如:15 能被除 1 与 15 以外的整数 3、 5 整除,15是一个合数。
特别地:数字 1 既不是素数,也不是合数。
素数求解的 N 种境界
-
依次遍历
程序设计
#include <stdio.h> int main() { int i = 0; for (i = 100; i <= 200; i++) { //printf("%d", i); //判断 i 是否为素数 int j = 0; for (j = 2; j < i; j++) { if (0 == i % j) break; } if (j == i) { printf("%d ", i); } } return 0; }
讯享网
程序运行示例
再设置一个计数器,加一个变量 count ,统计总共有几个素数
讯享网#include <stdio.h> int main() { int i = 0; int count = 0; for (i = 100; i <= 200; i++) { int j = 0; for (j = 2; j < i; j++) { if (0 == i % j) break; } if (j == i) { printf("%d ", i); count++; } } printf("\ncount = %d\n", count); return 0; }
![]()
-
排半法
打个响指,排除掉二分之一的可能!
理论上说,如果 i 存在一个大于 i/2 且小于 i 的因数,则必存在一个与之对应的小于 i/2 且大于 1 的因数,因而从判别功能来说,取到 i/2 已足够。
#include <stdio.h> int main() { int count = 0; for (int i = 100; i <= 200; i++) { int j = 0; //条件语句中的等号去掉,对逻辑结构有何影响 for (j = 2; j <= i / 2; j++) { if (0 == i % j) break; } if (j > i / 2) //注意这里为什么不是 >= { printf("%d ", i); count++; } } printf("\ncount = %d\n", count); return 0; }
j 循环条件中,j 的取值范围包含等号是因为:要考虑 j=i/2 的情况
当 j 大于 i/2 时,可以肯定 j 不是 i 的质因数;
-
开平方
理论上说,如果 i 存在一个大于 sqrt(i) 且小于 i 的因数,则必存在一个与之对应的小于 sqrt(i) 且大于 1 的因数,因而从判别功能来说,取到 sqrt(i) 已足够。
开平方 --> 使用函数 sqrt() ----> #include <math.h> ----> 数学库函数
讯享网#include <math.h> #include <stdio.h> int main() { int count = 0; for (int i = 100; i <= 200; i++) { int j = 0; //条件语句中的等号去掉,对逻辑结构有何影响 for (j = 2; j <= sqrt(i); j++) { if (0 == i % j) break; } if (j > sqrt(i)) //注意这里为什么不是 >= { printf("%d ", i); count++; } } printf("\ncount = %d\n", count); return 0; }

-
排除偶数
偶数绝不可能。先排除一个可能,素数(除了2)绝不会是偶数
#include <math.h> #include <stdio.h> int main() { int count = 0; for (int i = 101; i <= 200; i+=2) { int j = 0; //条件语句中的等号去掉,对逻辑结构有何影响 for (j = 2; j <= sqrt(i); j++) { if (0 == i % j) break; } if (j > sqrt(i)) //注意这里为什么不是 >= { printf("%d ", i); count++; } } printf("\ncount = %d\n", count); return 0; }

以上方案属于同一种方法:试除法(试商判别法),但都是普通版
-
试商判别法(终极版)
试商判别法是依据素数的定义来实施的。使用试除法来探求奇数 i (只有唯一偶素数 2,不作试商判别)是不是素数,用奇数 j (取 3,5,……,sqrt(i) )去试商。若存在某个 j 能整除 i,说明 i 能被 1 与 i 本身以外的整数 j 整除,i 不是素数。若在上述范围内的所有奇数 j 都不能整除 i, 则 i 为素数。
判别 j 整除 i 常用表达式 i % j = 0 实现
程序设计
讯享网#include <math.h> #include <stdio.h> int main() { long c, d, i, j, n, t; printf(" 求区间 [c, d] 上的素数:\n"); printf(" 请输入 c, d (c>2) :>_ "); scanf("%ld%ld", &c, &d); if (0 == c % 2) { c++; } n = 0; for (i = c; i <= d; i+=2) { for (t = 0, j = 3; j <= sqrt(i); j += 2) { if (0 == i % j) //实施试商 { t = 1; break; } } if (0 == t) //标志量 t = 0 时,i 为素数 { printf(" %ld", i); n++; //统计素数的个数 if (0 == n % 10) { printf("\n"); } } } printf("\n 共 %ld 个素数", n); return 0; }
程序运行示例

-
厄拉多塞筛法
厄拉多塞提出求素数的筛法:对于一个大整数 x,只要知道不超过 sqrt(x) 的所有素数 p,划去所有 p 的倍数 2p,3p,……,剩下的整数就是不超过 x 的全部素数
应用筛法求素数,为方便实施『划去』操作,应设置数组。每一数组元素对应一个带判别的奇数,并赋初值 0。如果该奇数为 p 的倍数则应划去,对应元素加一个划去标记,通常给该元素赋值 -1。最后,打印元素值不是 -1(即没有划去)的元素对应的奇数即所求素数
在实际应用筛法的过程中,p 通常不限于取不超过 sqrt(x) 的素数,而是取 3 到 sqrt(x) 的奇数。尽管多了一些重复划去的操作,但程序的实现要简单许多
应用筛法求素数设计要点
设置 a 数组存储区间中的所有奇数,凡『划去』的数组元素赋值 -1。
在指定区间 [c, d] (约定 c 为奇数)上所有奇数表示为 j = c + 2k 『k =0, 1, 2,…, e,这里 e = (d-c)/2』。于是k = (j - c)/2 是奇数 j 在数组中的序号(下标)。如果 j 为奇数的倍数时,对应数组元素作划去标记,即 a[ (j-c)/2 ] = -1。
根据 c 与奇数 i 确定 g = 2*int( c/(2*i) )+1,使得 gi 接近区间下限 c,从而使划去的 gi, (g+2)i, …在 [c, d] 中,减少无效操作,以提高对大区间的筛选效率。
最后,凡数组元素 a[k] ≠ -1,对应的奇数 j = c+2k 就为素数。
程序实现
#include <math.h> #include <stdio.h> //筛法求指定区间上的素数 int main() { long int c, d, e, g, i, j, k, n; static long int a[80000]; printf("求区间 [c, d] 上的素数:\n"); printf("请输入 c, d (c>2):"); scanf("%ld%ld", &c, &d); if (0 == c % 2) { c++; } e = (d - c) / 2; i = 1; while (i <= sqrt(d)) //在 [c, d] 中筛选素数 { i += 2; g = 2*(c/(2*i))+1; if (g*i > d) continue; if (1 == g) { g = 3; } j = i*g; while (j <= d) { if (j >= c) //筛去标记 -1 { a[(j - c) / 2] = -1; } j = 2 * i + j; } } for (n = 0, k = 0; k <= e; k++) { if (a[k] != -1) //输出所得素数 { n++; printf("%ld ", c + 2 * k); if (0 == n % 12) { printf("\n"); } } } printf("\n共 %ld 个素数\n", n); return 0; }
程序运行示例

小小总结:
比较以上求素数的两种方法,各有所长:试商法较为直观,设计容易实现,因此常为程序设计爱好者所用;筛法在较大区间的搜索与较大整数的判别上效率更高,但在设计上较难把握。
常见问题:
- 为什么我们整除用的是 取模符号 %:
判别 j 整除 i 常用表达式 i % j = 0 实现,因为当 i % j == 0时,余数为零,表示恰好整除。
- 变量太多,分辨不出
可以通过将过程中的某些代码块封装成函数来减少实参
- 其他问题
可以直接在评论区留言
版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容,请联系我们,一经查实,本站将立刻删除。
如需转载请保留出处:https://51itzy.com/kjqy/80992.html