C++中的素数判断方法及代码 |21xrx.com

2023-06-22 05:03:06 深夜i -- --

C++ 素数判断代码

在计算机科学中，素数是指只能被1和本身整除的正整数。判断一个数是否为素数是计算机程序中的基本问题之一。在C++编程语言中，有多种方法可以实现素数判断，本文将介绍其中两种方法，并提供相应的代码。

方法一：暴力枚举法

暴力枚举法是一种常用的初学者方法，也是最简单的方法之一。该方法的原理是：依次判断待判断的数x是否能被每个小于x的数整除，如果存在一个能整除的数，则x不是素数；否则，x是素数。

以下是暴力枚举法的代码：

bool is_prime(int x){

if(x<=1) return false;

for(int i=2;i

if(x%i==0)

return false;

}

return true;

}

以上代码中，先判断x是否小于等于1，如果是，返回false。然后以循环的形式，从2开始枚举小于x的正整数，如果存在一个能被x整除的数，则返回false，否则返回true。

方法二：埃氏筛法

埃氏筛法是一种常用的高效方法，在大数据量的情况下，优于暴力枚举法。该方法的原理是：先将所有的数标记为素数，然后筛除所有小于等于x的合数，最后留下的就是素数。

以下是埃氏筛法的代码：

void get_prime(int n){

int prime[n]={0},num=0;

bool is_prime[n+1]={true};

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

if(is_prime[i]){

prime[num++]=i;

}

for(int j=0;j <=n;j++){

is_prime[i*prime[j]]=false;

if(i%prime[j]==0) break;

}

for(int i=0;i

cout< <<" ";

}

以上代码中，先定义一个长度为n的数组prime，用于存储素数，以及一个长度为n+1的布尔数组is_prime，初始值为true。依次从2到n枚举，如果is_prime[i]为true，则将i添加到prime数组中，并将is_prime[i]的倍数标记为false。

使用方法

以上是C++中素数判断的两种方法及代码。对于方法一，只需调用函数is_prime(x)，即可判断x是否为素数；而对于方法二，则需调用函数get_prime(n)，即可获取小于等于n的所有素数。在处理大量数据时，可以使用方法二，以提高程序执行效率。

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

下一篇: C++重载矩阵乘法

()

相似文章