C++中素数的判断与求法 |21xrx.com

C++中素数的判断与求法

2023-07-04 10:53:15 深夜i -- --

C++ 素数判断求法

C++是一门功能强大的编程语言，可以用来解决许多数学和计算问题。其中包括素数的判断和求解。在本文中，我们将介绍C++中判断素数和求解素数的两种方法。

1.素数的判断方法

方法1:利用质数的定义，素数必须是大于1的自然数，只能被1和自身整除。

因此，我们可以用循环来判断一个数n是否是素数。具体实现代码如下：


bool isPrime(int n){
if(n<=1) return false; //小于等于1均不为素数
for(int i=2;i*i<=n;i++){ //只需要循环到n的平方根
if(n%i==0) return false;
}
return true;
}

方法2:优化素数判断，只需要判断n是否能被2和3整除。其它的素数必定是6x+1或者6x-1(x>0)的形式，所以只需要判断这些数是否能被n整除。

具体实现代码如下：


bool isPrime(int n){
if(n<=3) return n>1; //小于等于3均为素数
if(n%2==0||n%3==0) return false;
for(int i=5;i*i<=n;i+=6){
if(n%i==0||n%(i+2)==0) return false;
}
return true;
}

2.素数的求解方法

方法1:暴力枚举法，从2开始依次枚举所有整数，判断是否为素数。

具体实现代码如下：


vector<int> getPrimes(int n){
vector<int> res;
for(int i=2;i<=n;i++){
if(isPrime(i)) res.push_back(i);
}
return res;
}

方法2:埃拉托色尼筛法，从2开始依次枚举所有正整数，如果当前数是素数，则将其所有的倍数标记为合数，最后留下来的即为素数。

具体实现代码如下：


vector<int> getPrimes(int n){
vector<bool> isPrime(n+1,true);
vector<int> res;
for(int i=2;i<=n;i++){
if(isPrime[i]){
res.push_back(i);
for(int j=i*i;j<=n;j+=i){
isPrime[j]=false;
}
}
}
return res;
}

总结：

本文介绍了C++中判断素数和求解素数的两种方法。对于简单的问题来说，可以使用暴力枚举法和质数定义法，但对于大量数据的处理，则可以使用优化的算法，如埃拉托色尼筛法。对于程序的复杂度，需要在程序中考虑清楚，保证程序的效率。这些方法不仅可以帮助我们更好地理解素数，而且对于提高算法能力和编程水平也是非常有帮助的。

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

下一篇: C++中数据成员的初始化方法详解

评论区

()

相似文章