【知识点4】素数(质数)

2024-06-30 20:25| 来源: 网络整理| 查看: 265

目录 1. 素数的概念2. 素数的判断3. 素数表的获得3.1 暴力3.2 性能优化——筛法 4. 注意点5. 题型训练6. 参考资料

1. 素数的概念

素数又称质数，是指除了1和本身之外，不能被其他数整除的一类数，反之，则称为合数。

注意：小于等于1的数既不是素数，也不是合数。

本节将解决两个问题：

如何判断给定的正整数n是否是质数；如何在较短的时间内得到1~n内的素数表。 2. 素数的判断

解法一：暴力。由素数的定义可以遍历从2 ~ n-1的数，判断它们是否可以整除n。但是这样时间复杂度就到达了 O ( n ) O(n) O(n)，通常判断素数只会作为程序的一部分，所以这样的时间复杂度还是有点高。

解法二：开根号。如果在2 ~ n-1中存在n的约数，不妨设为k，即n % k == 0，那么由 k * （n / k）== n可知，n/k也是n的一个约数，且k与n/k中一定满足其中一个小于等于 n \sqrt n n ，一个大于等于 n \sqrt n n 。这样我们只要判断2 ~ n \sqrt n n 之间的整数就好了，时间复杂度为 O ( n ) O(\sqrt n) O(n )。

代码如下：

bool isPrime(int n){ if(n if(n % i == 0){ //注意是取余，而不是除法 return false; } } return true; //否则，就是true }

注意：

上述代码中，sqrt()的作用为一个浮点数开根号，需要添加math.h头文件。由于sqrt的参数要求是浮点数，因此在n前面乘以1.0来使其变成浮点数。isPrime()一定要记得特判小于等于 1 1 1不是质数！！！ 3. 素数表的获得 3.1 暴力

通过上面的学习，我们知道了怎么判断一个数n是否是素数，那么我们如果要统计1 ~ n之间的素数也就清楚了，算法的时间复杂度为 O ( n n ) O(n\sqrt n) O(nn )，当我们的数据n小于 1 0 5 10^5 105时，这种算法是不会超时的。代码如下：

const int maxn = 101; //步长 int prime[maxn],pNum = 0; //prime数组存放所有的素数，pNum用于存储素数数量 bool p[maxn] = {0}; //p[i] == true表示i是素数 void Find_Prime(){ for(int i = 1;i prime[pNum++] = i; p[i] = true; } } }

数据结构：

int prime[]用于存储所有的素数；bool p[]用于快速判断某一个数是否为素数；pNum用于记录素数的数量。 3.2 性能优化——筛法

我们使用下面的“筛法”，达到时间复杂度为 O ( n l o g l o g n ) O(nloglogn) O(nloglogn)。在这里插入图片描述 "筛"的实现，可以使用一个bool型数组p来标记，如果a被筛掉，那么设置p[a]为true；否则，p[a]为false。程序初始化时，记得初始化p数组全为false。代码如下：

const int maxn = 101; int prime[maxn],pNum = 0; bool p[maxn] = {0}; void Find_Prime(){ for(int i = 2;i //如果i是素数 prime[pNum++] = i; //把素数i存放到prime数组中 for(int j = i+i;j

【本文地址】

公司简介

联系我们