C++中如何判断一个数是否为素数？ |21xrx.com

C++中如何判断一个数是否为素数？

2023-06-25 07:09:45 深夜i -- --

C++ 素数判断

在C++中判断一个数是否为素数，需要用到一个数学概念——质数。所谓质数，指的是只能被1和自身整除的正整数。判断一个数是否为素数有许多种方法，以下是其中的一些方法：

方法一：暴力枚举

对于一个正整数n，如果它可以被2到n-1之间的任何一个正整数整除，则说明它不是素数。如果它不能被任何一个正整数整除，则说明它是素数。

具体来说，用一个循环从2到n-1枚举所有可能的因子，如果发现某个因子可以整除n，则n不是素数。如果循环结束后还没有找到除1和n外的因子，则n是素数。

实现方法如下：

bool isPrime(int n) {

if (n < 2) return false; //小于2的数不是素数

for (int i=2; i

if (n%i == 0) return false;//找到因子，不是素数

}

return true;//没有找到因子，是素数

}

方法二：优化枚举法

方法一的缺点在于需要枚举大量的数，当n很大时，运算速度会变得很慢。这时，我们可以进行优化。

优化的方法是，我们只需要枚举2到sqrt(n)之间的整数即可。这是因为，如果n不是素数，那么它一定有一个大于1小于等于sqrt(n)的因子。假设这个因子是d，那么n/d也一定是n的因子，且n/d大于等于sqrt(n)。因此，如果n不能被2到sqrt(n)之间的任何一个整数整除，则n是素数。

实现方法如下：

bool isPrime(int n) {

if (n < 2) return false;

for (int i=2; i<=sqrt(n); i++) {

if (n%i == 0) return false;//找到因子，不是素数

}

return true;//没有找到因子，是素数

}

方法三：筛法

在计算机科学中，有一种方法可以快速求解一个区间内的所有素数，它就是著名的埃拉托斯特尼筛法。这个算法的基本思想是，从2开始，将每个质数的倍数都标记成合数，以达到筛选素数的目的。

具体实现过程如下：

（1）先将2~N的各数放入表中，然后在2的上面画一个圆圈，把2的倍数（除了2本身以外）都筛掉；

（2）再找到表中未被筛掉的下一个数p，然后把它的倍数都筛掉；（因为如果p是合数，则它的倍数一定也是合数，所以不需要考虑它们是否为合数）

（3）重复上述操作，直到筛完所有小于等于N的数。

实现如下：

const int MAXN=10000000;

int prime[MAXN],num=0;//保存素数的数组

void get_prime() {//筛选素数

bool is_prime[MAXN];//标记是否为素数

memset(is_prime, true, sizeof(is_prime));//初始化

for (int i=2; i<=MAXN; i++) {

if (is_prime[i]) {

prime[num++]=i;//将素数保存到数组中

for (int j=i+i; j<=MAXN; j+=i) {//当前数的倍数一定不是素数，标记

is_prime[j]=false;

}

使用以上三种方法判断一个数是否为素数。方法一适用于数据规模较小的情况，方法二将枚举的数据量减少了一半，效率更高。方法三适用于大量素数的筛选，但需要开较大的数组空间，而且只能处理固定范围内的素数。根据不同的情况选择不同的方法，可以使程序更加高效。

上一篇: idea打包java可执行jar包

下一篇: 如何在C++中输出内存占用？

评论区

()

相似文章