提供判断素数的2种算法,要求写出算法伪代码和C/C++描述

当然，我可以介绍两种常见的判断素数的算法，一种是简单的暴力判断法，另一种是著名的埃拉托斯特尼筛法。

**1. 暴力判断法 (试除法)**

这个方法适用于较小的数字，其基本思想是从2开始，一直测试到数字本身是否能整除它。如果能整除，那么就不是素数，否则是素数。

**暴力判断法伪代码:**

function isPrime(n):
    if n <= 1:
        return false
    for i from 2 to sqrt(n):
        if n % i == 0:
            return false
    return true

**C/C++ 描述:**

bool isPrime(int n) {
    if (n <= 1)
        return false;
    for (int i = 2; i * i <= n; ++i) {
        if (n % i == 0)
            return false;
    }
    return true;
}

**2. 埃拉托斯特尼筛法 (Sieve of Eratosthenes)**

这是一种更高效的筛选大范围素数的方法，通过遍历从2开始的所有数，每次去除所有该数倍数的数，直到达到最大值。

**埃拉托斯特尼筛法伪代码:**

function sieveOfEratosthenes(n):
    primes[0] = primes[1] = false
    for p from 2 to sqrt(n):
        if primes[p]:
            for i from p^2 to n with step p:
                primes[i] = false
    primes[2..sqrt(n)] = true
    result = [p for p in range(2, n+1) if primes[p]]

**C/C++ 描述:**

void sieveOfEratosthenes(int n, vector<bool>& primes) {
    primes.resize(n + 1, true);
    for (int p = 2; p * p <= n; ++p) {
        if (primes[p]) {
            for (int i = p * p; i <= n; i += p)
                primes[i] = false;
        }
    }
    for (int p = 2; p < n; ++p) {
        if (primes[p])
            result.push_back(p);
    }
}