L1-028 判断素数 C++

### C++ 实现判断素数方法

在C++中，可以通过多种方式实现判断一个数是否为素数的功能。以下是几种常见的实现方案。

#### 方法一：基本遍历法
通过遍历从2到`sqrt(n)`之间的所有整数来检测是否存在能整除给定数值的情况。这种方法简单直观，适用于大多数场景下的素数判定需求[^1]。

#include <iostream>
#include <cmath>

bool isPrime(int num) {
    if (num <= 1) return false;
    for (int i = 2; i <= std::sqrt(num); ++i) {
        if (num % i == 0) return false;
    }
    return true;
}

int main() {
    int number;
    std::cout << "请输入一个数：" << std::endl;
    std::cin >> number;

    if(isPrime(number)){
        std::cout << number << " 是素数" << std::endl;
    }else{
        std::cout << number << " 不是素数" << std::endl;
    }

    return 0;
}

#### 方法二：优化后的遍历法
此版本同样基于遍历的思想，但在细节上做了改进。比如提前排除偶数情况，并且只考虑奇数因子，从而减少不必要的计算次数[^3]。

#include <iostream>
#include <cmath>

bool check_prime(int value){
    if(value<2)return false;
    if(value%2==0)return value==2;//处理特殊情况
    
    double limit=sqrt(static_cast<double>(value));
    
    for(int divisor=3;(divisor<=limit)&&!(value%divisor);divisor+=2);
        
    return !(value>static_cast<int>(limit));  
}

// 主函数部分保持不变...

#### 方法三：利用费马小定理的概率性检验
虽然这种方法不是绝对可靠的（因为存在伪素数现象），但对于某些特定应用场合来说可能是有效的选择之一[^4]。

#include <iostream>
using namespace std;

long long powerMod(long long base, long long exp, long long mod) {
    long long result = 1;
    while(exp > 0) {
        if(exp & 1)
            result = (result * base) % mod;
        exp >>= 1;
        base = (base * base) % mod;
    }
    return result;
}

bool fermatTest(int p) {
    if(p == 2 || p == 3) return true;
    if(p <= 1 || p % 2 == 0) return false;
    
    // 测试多个底数a以提高准确性
    const int TEST_COUNT = 5;
    for(int round = 0; round < TEST_COUNT; ++round) {
        int a = rand()%(p-3)+2;
        if(powerMod(a,p-1,p)!=1){
            return false;
        }
    }
    return true;
}

// 使用fermatTest代替之前的isPrime逻辑即可...