C++判断素数方法

一、什么是素数

素数是只能被1和自身整除的数，比如2、3、5、7、11等。判断一个数是否为素数一直是数学里的一个热门问题，也是我们在算法和编程中经常遇到的问题之一。

二、判断素数的方法

C++中常用的判断素数的方法有两种：试除法和Eratosthenes筛法。

三、试除法

试除法是最基本的判断素数的方法，其思想是：用2~(n-1)的整数去除n，如果都除不尽，那么n就是素数。C++代码如下：

bool isPrime(int n){
    for(int i=2;i


   
这种方法虽然简单易懂，但效率较低，当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<<<" ";
        }
    }
}

   

使用Eratosthenes筛法判断素数的时间复杂度为O(nloglogn)，比试除法效率高很多。

五、总结
以上是C++常用的两种判断素数的方法，试除法简单易懂但效率较低，适用于小数判断。Eratosthenes筛法复杂度较低，适用于大数判断。在实际应用中，应根据具体情况选择合适的方法。