质数(素数)的几种判断方法

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

相关文章

Python实现无痛修改第三方库源码的方法详解

《Python实现无痛修改第三方库源码的方法详解》很多时候,我们下载的第三方库是不会有需求不满足的情况,但也有极少的情况,第三方库没有兼顾到需求,本文将介绍几个修改源码的操作,大家可以根据需求进行选择... 目录需求不符合模拟示例 1. 修改源文件2. 继承修改3. 猴子补丁4. 追踪局部变量需求不符合很

Flutter打包APK的几种方式小结

《Flutter打包APK的几种方式小结》Flutter打包不同于RN,Flutter可以在AndroidStudio里编写Flutter代码并最终打包为APK,本篇主要阐述涉及到的几种打包方式,通... 目录前言1. android原生打包APK方式2. Flutter通过原生工程打包方式3. Futte

mysql出现ERROR 2003 (HY000): Can‘t connect to MySQL server on ‘localhost‘ (10061)的解决方法

《mysql出现ERROR2003(HY000):Can‘tconnecttoMySQLserveron‘localhost‘(10061)的解决方法》本文主要介绍了mysql出现... 目录前言:第一步:第二步:第三步:总结:前言:当你想通过命令窗口想打开mysql时候发现提http://www.cpp

Mysql删除几亿条数据表中的部分数据的方法实现

《Mysql删除几亿条数据表中的部分数据的方法实现》在MySQL中删除一个大表中的数据时,需要特别注意操作的性能和对系统的影响,本文主要介绍了Mysql删除几亿条数据表中的部分数据的方法实现,具有一定... 目录1、需求2、方案1. 使用 DELETE 语句分批删除2. 使用 INPLACE ALTER T

MySQL INSERT语句实现当记录不存在时插入的几种方法

《MySQLINSERT语句实现当记录不存在时插入的几种方法》MySQL的INSERT语句是用于向数据库表中插入新记录的关键命令,下面:本文主要介绍MySQLINSERT语句实现当记录不存在时... 目录使用 INSERT IGNORE使用 ON DUPLICATE KEY UPDATE使用 REPLACE

Python实现Microsoft Office自动化的几种方式及对比详解

《Python实现MicrosoftOffice自动化的几种方式及对比详解》办公自动化是指利用现代化设备和技术,代替办公人员的部分手动或重复性业务活动,优质而高效地处理办公事务,实现对信息的高效利用... 目录一、基于COM接口的自动化(pywin32)二、独立文件操作库1. Word处理(python-d

CentOS 7部署主域名服务器 DNS的方法

《CentOS7部署主域名服务器DNS的方法》文章详细介绍了在CentOS7上部署主域名服务器DNS的步骤,包括安装BIND服务、配置DNS服务、添加域名区域、创建区域文件、配置反向解析、检查配置... 目录1. 安装 BIND 服务和工具2.  配置 BIND 服务3 . 添加你的域名区域配置4.创建区域

mss32.dll文件丢失怎么办? 电脑提示mss32.dll丢失的多种修复方法

《mss32.dll文件丢失怎么办?电脑提示mss32.dll丢失的多种修复方法》最近,很多电脑用户可能遇到了mss32.dll文件丢失的问题,导致一些应用程序无法正常启动,那么,如何修复这个问题呢... 在电脑常年累月的使用过程中,偶尔会遇到一些问题令人头疼。像是某个程序尝试运行时,系统突然弹出一个错误提

电脑提示找不到openal32.dll文件怎么办? openal32.dll丢失完美修复方法

《电脑提示找不到openal32.dll文件怎么办?openal32.dll丢失完美修复方法》openal32.dll是一种重要的系统文件,当它丢失时,会给我们的电脑带来很大的困扰,很多人都曾经遇到... 在使用电脑过程中,我们常常会遇到一些.dll文件丢失的问题,而openal32.dll的丢失是其中比较

python中字符串拼接的几种方法及优缺点对比详解

《python中字符串拼接的几种方法及优缺点对比详解》在Python中,字符串拼接是常见的操作,Python提供了多种方法来拼接字符串,每种方法有其优缺点和适用场景,以下是几种常见的字符串拼接方法,需... 目录1. 使用 + 运算符示例:优缺点:2. 使用&nbsjsp;join() 方法示例:优缺点:3