2025年学习篇 - 『素数』查找方式总结

学习篇 - 『素数』查找方式总结导语 本篇博客中含有大量的 C 语言基础知识及算法 算法有两类 试商判别法 和 厄拉多塞筛法 目录 导语 什么是素数 素数求解的 N 种境界 依次遍历 排半法 开平方 排除偶数 试商判别法 终极版 厄拉多塞筛法

大家好,我是讯享网,很高兴认识大家。

导语:

本篇博客中含有大量的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时,余数为零,表示恰好整除。

  • 变量太多,分辨不出

可以通过将过程中的某些代码块封装成函数来减少实参

  • 其他问题

可以直接在评论区留言

 


 

小讯
上一篇 2025-04-06 21:04
下一篇 2025-02-16 10:06

相关推荐

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容,请联系我们,一经查实,本站将立刻删除。
如需转载请保留出处:https://51itzy.com/kjqy/80992.html