质数（素数）的几种判断方法

2024-06-12 17:28
文章标签 方法 判断 质数 几种 素数

本文主要是介绍质数（素数）的几种判断方法，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

判断一个数是否为质数/合数是在数据处理中经常遇到的问题，如何解决这个问题，作者总结了如下几种算法。

质数的定义：

一个数如果除了1 和 其本身外，不能被其它数整除，就称这个数为质数（或素数）。

合数的定义：

一个数除了1和其本身外，还可以被其它数整除，那么就称这个数为合数。

  • 第一种：枚举法

这个方法的思想就是利用质数的定义来进行枚举判定。例如，判断数字N是否为质数，那么就逐一判断2～N-1 范围内的每一个数，是否可以被N整除，只要在这个范围内存在任意一个可以被N整除的数，就称N 为非质数。

//代码段1//10000内的所有质数的个数#include <stdio.h>
#define MAX_N 10000int is_prime(int n){for(int i = 2;i < n-1;i++){if(n % i == 0) return 0;}return 1;
}
int main(){int count = 0;for(int i = 2;i <= MAX_N;i++){if(is_prime(i)) ++count ;}printf("num is %d\n",count);return 0;
}

运行结果：

 

在10000以内，存在1229个质数，运行这段枚举代码用了0.21秒。 

枚举法分析：

优点：通过定义去判断，代码实现思路易于理解；

缺点：如果数据范围较大，即N值较大，在2～N-1 范围内逐一枚举，判断枚举值是否可以被N值整除，效率较低；

  • 第二种 优化枚举法

第一种方法的缺点显而易见，在进行枚举判断时的枚举范围是2～N-1， 缩小枚举范围就是优化方向。

我们知道，如果一个数N是合数，那么一定存在这样的关系：N = a*b （a和b 均不等于1 或者N本身） ，且因为存在 N = \sqrt{N} * \sqrt{N}；所以，a 一定大于或等于 \sqrt{N}， 而b一定小于或等于\sqrt{N}，不存在a和b同时大于或同时小于\sqrt{N}的情况。因此，枚举范围可以修改为2～\sqrt{N}， 因为，如果N是合数，那么在这个范围内必然存在一个它的因子。

//代码段2//10000内所有质数的总个数#include <stdio.h>
#include <math.h>#define MAX_N 10000int is_prime(int n){for(int i = 2，I = sqrt(n);i<= I;i++){if(n % i == 0) return 0;}return 1;
}int main(){int count = 0;for(int i = 2;i <= MAX_N;i++){if(is_prime(i)) ++count;}printf("num is %d\n",count);return 0;
}

运行结果：

将枚举范围由2～N-1 缩小到2～\sqrt{N} 后，运行时间由0.21缩短到0.002秒。

优缺点分析：

优点：通过缩小枚举范围，运行时间得到了显著提成；

缺点：时间复杂度依然是0（n*n）

小技巧：

在下述代码段中，如果数据规模是100000， 那么采用优化前的“代码段A”，程序的运行时间为0.25秒，如果采用优化后的“代码段B”，程序的运行时间为0.11秒，这是因为函数sqrt在代码段A中被调用了sqrt(n)次，执行了sqrt(n)  次的函数入栈出栈操作，但是在代码段B，sqrt函数只执行了一次。

//代码段3//优化前，代码段A：
int is_prime(int n){for(int i = 2; i<= sqrt(n);i++){if(n % i == 0) return 0;}return 1;
}//优化后，代码段B：
int is_prime(int n){for(int i = 2，I = sqrt(n);i<= I;i++){if(n % i == 0) return 0;}return 1;
}
  • 第三种 素筛法

素筛法是通过逐步排除合数来识别素数的一种数学算法。

总体思想：

用素数去标记掉所有不是素数的数字，如果i是素数，那么所有i 的整数倍就不是素数。

代码实现思路：

1. 构建一个额外的数据存储空间  int prime[N]；

2. 用pirme[i] 来标记i是否为合数；

3. 第一次知道2 是素数，则将2的倍数都标记为1；

4. 向后找到第一个没有被标记的数字i；

5.将i的倍数全部标记为合数；

6. 重复4-5步，直到标记为你范围内的所有数字；

//代码段4#include <stdio.h>#define MAX_N 100
int prime[MAX_N+5] = {0};
void init_prime(){for(int i = 2;i <= MAX_N;i++){if(prime[i] == 0){for(int j = 2, I = MAX_N/i; j <= I; j++){ //如果运行的这个行，表示i为质数；prime[j*i] = 1; // 将i的整数倍的值，都标记} }}return;
}
int main(){init_priem(); int cnt = 0; //用于计数，统计0～MAX_N 范围内有有多少个质数；for(int i = 2;i <= MAX_N;i++){if(prime[i] == 0) ++cnt;}printf("num is %d\n",cnt);return 0;
}

素筛法优化 之一

在代码段4 的init_prime() 函数中存在多层缩紧，为了提高代码的可读性，采用名为“对偶逻辑”

的编程技巧，所谓“对偶逻辑”就是对立的逻辑。

//代码段5
void init_prime(){for(int i = 2;i <= MAX_N;i++){if(prime[i]) continue;for(int j = 2, I = MAX_N/i; j <= I; j++){ prime[i*j] = 1;}}return;
}

素筛法优化 之二

当前的init_prime() 函数已经做到了对数据范围内的所有数值进行了是否为质数的判断，如果i为质数，则prime[i] 等于0， 如果i为合数，则pirme[i] 为1.

是否可以将筛查出的质数保存到一个数据结构中？当然可以。

思路1: 申请一个数组， int primeValue[MAX_N+5] = {0}; 则 primeValue[0] = 2; primeValue[1] = 3;primeValue[2] = 5; ... 但是这么做增加了内存空间的开销；

思路2: 不额外的申请内存 ，只使用  int prime[MAX_N+5]

// 代码段6
#include <stdio.h>#define MAX_N 100000int prime[MAX_N+5] = {0};void init_Prime(){for(int i = 2;i <= MAX_N;i++){if(prime[i]) continue;prime[++Prime[0]] = i; // 如果执行到这一行，说明i为质数，从prime[1] 开始依次存放找到的质数；++Prime[0] 说明每找到一个质数，prime[0]的值加1，当函数执行完毕，prime[0]代表质数的总个数for(int j = 2,I =MAX_N/i; j<=I; j++){prime[i*j] = 1;}}
}int main(){init_prime();for(int i = 1;i <= prime[0];i++){printf("%d ", prime[i]);if(i % 10 == 0) printf("\n"); // 一行打印10个数据；}return 0;
}

素筛法应用举例

例题1: 求出一个范围内（假设20）所有数字的最小素因子

解析：一个质数 N , 它只有1和它本身两个因子，因此它只存在一个因式 N = 1*N， 又因为1为非质数，所以质数N的最小素因子就是其本身。

编程思路：利用素筛法

#include <stdio.h>
#define MAX_N 20int prime[MAX_N+5] = {0}; //存放对应数据的素因子；void init_prime(){for(int i = 2;i <= MAX_N;i++){if(prime[i]) continue;prime[i] = i; //i为质数，最小素因子即为i本身for(int j = 2, I <= MAX_N/i; j<=I; j++){if(prime[i*j]) continue; //如果已经被标记过，说明存储了最小素因子；prime[i*j] = i;}}return;
}int main(){init_prime();for(int i = 2;i<= MAX_N;i++){printf("min[%d] = %d\n",i, prime[i]);}return 0;
}

运行结果：

例题1: 求出一个范围内（假设20）所有数字的最大素因子 

解析：例如 数据 20，它的因式可有表示为：2*10； 5*4； 所以它的最大素因子就是5；

#include <stdio.h>#define MAX_N 20
int prime[MAX_N] = {0};void init_prime(){for(int i  = 2; i <= MAX_N;i++){if(prime[i]) continue;prime[i] = i;for(int j = 2, I=MAX_N/i; j<=I; j++){prime[i*j] = i;}}}int main(){init_prime();for(int i = 2;i <= MAX_N;i++){printf("MAX(%d) = %d\n",i, prime[i]);}return 0;}

运行结果：

  • 第四种 线性筛算法

在上述素筛法的实现过程中，存在数据被多次标记的情况。

例如：合数6被标记了几次？当前质数为2时，标记2的倍数，6被标记了一次，当执行到质数3时，6作为3的倍数，又被标记了一次，所以，6被标记了2次。

通过分析，一个存在m个质数因子的合数，将被标记m次 （参考代码6的init_prime() 函数）。

例如：30 被标记了几次？30存在的质数因子为：2，3，5，所以，它将被标记3次。

为了解决合数被重复标记的问题，可以采用线性筛算法。

算法思想：

1. 标记一个范围内的数字是否为合数，没有被标记的则为素数。

2. 算法的空间复杂度为O(N), 时间复杂度为O(N)

3. 一个合数N的n个因子中，最小的那个素数因子p，被称为最小素因子，线性筛算法的思想就是用满足等式N=m*p的中的m去标记N。同样以30为例，它的所有因式如下：

因式1:   1*30

因式2:   2*15

因式3:   3*10

因式4:   5*6

因式5:   6*5

因式6:  10*3

因式7:  15*2

因式8:  30*1

由于因式1和因式8是由 数字1和它本身构成，不予考虑。如果使用素筛法时，参见代码段6的init_prime() 函数，当i = 2，3，5时，30都会被标记一次，但是线筛法的思想是，找到最小素因子2所对应的因子15，用15*2 标记出30，因为15是30的最大因子，是30的对后一个因式，是i值循环加加的过程中，最后一次得到30的机会，用来标记30，30的有且一次的标记机会。

所以，N和m有如下性质：

1. N中最小的素数为p

2. N可以表示成P*m

3. p一定小于等于m中最小的素因子（即：m不是p的整数倍，如果m是p的整数倍，那么p就不是N的最小素因子）

4. 利用M*{p}' （所有不大于m中最小素数的集合）标记N1，N2，N2....

代码实现

#include <stdio.h>#define MAX_N 100int prime[MAX_N+5] = {0};void init_prime(){for(int i = 2;i <= MAX_N;i++){  // i值为mif(!prime[i]) prime[++prime[0]] = i;for(int j = 1;j <= prime[0]; j++){if(prime[j] *i > MAX_N) break;prime[prime[j]*i] = 1;  // 通过m*p 找到对应的N if(i % prime[j] == 0) break;}}return 0;
}int main(){init_prime();for(int i = 1;i <= prime[0]; i++){printf("%d\n",prime[i]);}return 0;
}

线性筛算法应用：

题目： 所有小于10的质数的和是2+3+5+7 = 17。求所有小于两百万的质数的和。

解析：

第一步：求出200万内的质数

第二步：求出质数和

//利用线性筛算法求200万内的质数和#include <stdio.h>#define MAX_N 2000000int prime[MAX_N+5] = {0}void init_prime(){for(int i = 0;i <= MAX_N; i++){if(!prime[i]) prime[++prime[0]] = i;for(int j = 1; j < prime[0];j++){if(prime[j]*i > MAX_N) break;prime[prime[j]*i] = 1;if(i % prime[j] == 0) break;}}return;
}init main(){long long sum = 0;for(int i = 1; i <= prime[0]; i++){sum += prime[i];}printf("sum = %lld\n",sum);return 0;
}

这篇关于质数（素数）的几种判断方法的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/1054863。

相关文章

问题：第一次世界大战的起止时间是 #其他#学习方法#微信

问题：第一次世界大战的起止时间是 #其他#学习方法#微信

问题：第一次世界大战的起止时间是 A.1913 ~1918 年 B.1913 ~1918 年 C.1914 ~1918 年 D.1914 ~1919 年 参考答案如图所示
阅读更多...
[word] word设置上标快捷键 #学习方法#其他#媒体

[word] word设置上标快捷键 #学习方法#其他#媒体

word设置上标快捷键 办公中，少不了使用word，这个是大家必备的软件，今天给大家分享word设置上标快捷键，希望在办公中能帮到您！ 1、添加上标 在录入一些公式，或者是化学产品时，需要添加上标内容，按下快捷键Ctrl+shift++就能将需要的内容设置为上标符号。 word设置上标快捷键的方法就是以上内容了，需要的小伙伴都可以试一试呢！
阅读更多...
大学湖北中医药大学法医学试题及答案，分享几个实用搜题和学习工具 #微信#学习方法#职场发展

大学湖北中医药大学法医学试题及答案，分享几个实用搜题和学习工具 #微信#学习方法#职场发展

今天分享拥有拍照搜题、文字搜题、语音搜题、多重搜题等搜题模式，可以快速查找问题解析，加深对题目答案的理解。 1.快练题 这是一个网站 找题的网站海量题库,在线搜题,快速刷题~为您提供百万优质题库,直接搜索题库名称,支持多种刷题模式:顺序练习、语音听题、本地搜题、顺序阅读、模拟考试、组卷考试、赶快下载吧! 2.彩虹搜题 这是个老公众号了 支持手写输入，截图搜题，详细步骤，解题必备
阅读更多...
Java面试八股之怎么通过Java程序判断JVM是32位还是64位

Java面试八股之怎么通过Java程序判断JVM是32位还是64位

怎么通过Java程序判断JVM是32位还是64位 可以通过Java程序内部检查系统属性来判断当前运行的JVM是32位还是64位。以下是一个简单的方法： public class JvmBitCheck {public static void main(String[] args) {String arch = System.getProperty("os.arch");String dataM
阅读更多...
电脑不小心删除的文件怎么恢复？4个必备恢复方法！

电脑不小心删除的文件怎么恢复？4个必备恢复方法！

“刚刚在对电脑里的某些垃圾文件进行清理时，我一不小心误删了比较重要的数据。这些误删的数据还有机会恢复吗？希望大家帮帮我，非常感谢！” 在这个数字化飞速发展的时代，电脑早已成为我们日常生活和工作中不可或缺的一部分。然而，就像生活中的小插曲一样，有时我们可能会在不经意间犯下一些小错误，比如不小心删除了重要的文件。 当那份文件消失在眼前，仿佛被时间吞噬，我们不禁会心生焦虑。但别担心，就像每个问题
阅读更多...
邮件群发推送的方法技巧？有哪些注意事项？

邮件群发推送的方法技巧？有哪些注意事项？

邮件群发推送的策略如何实现？邮件推送怎么评估效果？ 电子邮件营销是现代企业进行推广和沟通的重要工具。有效的邮件群发推送不仅能提高客户参与度，还能促进销售增长。AokSend将探讨一些关键的邮件群发推送方法和技巧，以帮助企业优化其邮件营销策略。 邮件群发推送：目标受众 了解他们的需求、兴趣和行为习惯有助于你设计出更具吸引力和相关性的邮件内容。通过收集和分析数据，创建详细的客户画像，可以更精
阅读更多...
上采样(upsample)的方法

上采样(upsample)的方法

上采样(upsample)的方法   在神经网络中，扩大特征图的方法，即upsample/上采样的方法   1）unpooling：恢复max的位置，其余部分补零   2）deconvolution(反卷积)：先对input补零，再conv   3）插值方法，双线性插值等；   4）扩张卷积，dilated conv；
阅读更多...
LeetCode--204 计数质数

LeetCode--204 计数质数

题目 统计所有小于非负整数 n 的质数的数量。 示例 示例:输入: 10输出: 4解释: 小于 10 的质数一共有 4 个, 它们是 2, 3, 5, 7 。 class Solution {public:int countPrimes(int n) {if (n <= 2) return 0;int cnt = 0;vector<bool> isPrime(n, true);
阅读更多...
青龙面板部署通用教程，含服务器、路由器、X86等部署方法

青龙面板部署通用教程，含服务器、路由器、X86等部署方法

1. 拉取镜像/更新镜像 docker pull whyour/qinglong:latest 2. 删除镜像 docker rmi whyour/qinglong:latest 3. 启动容器 普通服务器 docker run -dit \-v $PWD/ql/config:/ql/config \-v $PWD/ql/log:/ql/log \-v $PWD/ql/db:
阅读更多...
# bash: chkconfig: command not found 解决方法

# bash: chkconfig: command not found 解决方法

bash: chkconfig: command not found 解决方法 一、chkconfig 错误描述： 这个错误表明在 Bash 环境下，尝试执行 chkconfig 命令，但是系统找不到这个命令。chkconfig 命令是一个用于管理 Linux 系统中服务的启动和停止的工具，通常它是 initscripts 包的一部分，但在最新的 Linux 发行版中可能已经被 syste
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2