一、什么是素数
素数是只能被1和自身整除的数，比如2、3、5、7、11等。判断一个数是否为素数一直是数学里的一个热门问题，也是我们在算法和编程中经常遇到的问题之一。
二、判断素数的方法
C++中常用的判断素数的方法有两种：试除法和Eratosthenes筛法。
三、试除法
试除法是最基本的判断素数的方法，其思想是：用2~(n-1)的整数去除n，如果都除不尽，那么n就是素数。C++代码如下：
bool isPrime(int n){
for(int i=2;i<n;i++){
if(n%i==0) return false; // 如果n能被i整除，说明n不是素数
}
return true;
}
这种方法虽然简单易懂，但效率较低，当n很大时，计算量会非常大。
四、Eratosthenes筛法
Eratosthenes筛法是一种比较高效的判断素数的方法，具体步骤如下：
1. 建立一个长度为n+1的bool数组is_prime，初始化为true。
2. 从2开始，依次将小于等于n的所有素数的倍数标记为false，这些数肯定不是素数。
3. 遍历数组，未被标记为false的数就是素数。
C++代码如下：
void eratosthenes(int n){
bool is_prime[n+1];
memset(is_prime,true,sizeof(is_prime)); // 将is_prime数组全部初始化为true
for(int i=2;i*i<=n;i++){ // 从2开始，标记小于等于n的所有素数的倍数为false
if(is_prime[i]){
for(int j=i*i;j<=n;j+=i){
is_prime[j]=false;
}
}
}
for(int i=2;i<=n;i++){ // 遍历数组，未被标记为false的数就是素数
if(is_prime[i]){
cout<<i<<" ";
}
}
}
使用Eratosthenes筛法判断素数的时间复杂度为O(nloglogn)，比试除法效率高很多。
五、总结
以上是C++常用的两种判断素数的方法，试除法简单易懂但效率较低，适用于小数判断。Eratosthenes筛法复杂度较低，适用于大数判断。在实际应用中，应根据具体情况选择合适的方法。
原创文章，作者：小蓝，如若转载，请注明出处：https://www.506064.com/n/304479.html
微信扫一扫 
支付宝扫一扫 