输出给定区间内的所有素数

思路分析

素数（质数）指大于1的自然数，且只能被1和自身整除。输出给定区间内的所有素数通常采用以下方法：

1. 暴力法：遍历区间内的每个数，检查是否为素数。检查时遍历2到该数的平方根，若存在能整除的数则非素数。
2. 埃拉托斯特尼筛法（筛法）：通过标记非素数的方式高效筛选素数，适合大范围区间。

方法1：暴力法（适合小范围）

暴力法直接检查每个数是否为素数。虽然简单，但时间复杂度较高（O(n√n)）。

代码实现

#include <iostream>
#include <cmath>
using namespace std;

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

void printPrimes(int start, int end) {
    for (int i = start; i <= end; i++) {
        if (isPrime(i)) {
            cout << i << " ";
        }
    }
    cout << endl;
}

int main() {
    int start, end;
    cout << "输入区间[start end]: ";
    cin >> start >> end;
    printPrimes(start, end);
    return 0;
}

代码详解

• isPrime函数检查数字是否为素数：
  • 若数字≤1，直接返回false。
  • 遍历2到sqrt(num)，若能整除则非素数。
• printPrimes遍历区间内的每个数，调用isPrime判断并输出素数。

方法2：埃拉托斯特尼筛法（适合大范围）

筛法通过预先标记非素数来高效筛选素数，时间复杂度为O(n log log n)。

代码实现

#include <iostream>
#include <vector>
using namespace std;

void sieveOfEratosthenes(int start, int end) {
    vector<bool> isPrime(end + 1, true);
    isPrime[0] = isPrime[1] = false;

    for (int i = 2; i * i <= end; i++) {
        if (isPrime[i]) {
            for (int j = i * i; j <= end; j += i) {
                isPrime[j] = false;
            }
        }
    }

    for (int i = start; i <= end; i++) {
        if (isPrime[i]) {
            cout << i << " ";
        }
    }
    cout << endl;
}

int main() {
    int start, end;
    cout << "输入区间[start end]: ";
    cin >> start >> end;
    sieveOfEratosthenes(start, end);
    return 0;
}

代码详解

• 初始化布尔数组isPrime，标记0和1为非素数。
• 从2开始遍历，若当前数为素数，则将其倍数标记为非素数（从i*i开始，步长为i）。
• 最后遍历区间，输出未被标记的数字。

注意事项

1. 输入范围：确保区间start和end合法（start ≤ end且end ≥ 2）。
2. 性能选择：
   • 小范围区间（如end < 10^6）可使用暴力法。
   • 大范围区间优先使用筛法。
3. 优化：筛法的空间复杂度为O(n)，可通过分段筛进一步优化内存。

常用实现方法对比

方法一：朴素筛法（试除法）

通过遍历区间内的每个数，逐一判断是否为素数。对于每个数n，检查2到√n之间的整数是否能整除n。

#include <iostream>
#include <cmath>
using namespace std;

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

void printPrimes(int start, int end) {
    for (int i = start; i <= end; i++) {
        if (isPrime(i)) {
            cout << i << " ";
        }
    }
    cout << endl;
}

int main() {
    int start = 10, end = 50;
    printPrimes(start, end);
    return 0;
}

方法二：埃拉托斯特尼筛法（Sieve of Eratosthenes）

通过标记非素数的方式高效筛选素数，适合处理大区间。需预先生成一个布尔数组标记非素数。

#include <iostream>
#include <vector>
using namespace std;

void sievePrimes(int start, int end) {
    vector<bool> isPrime(end + 1, true);
    isPrime[0] = isPrime[1] = false;
    for (int i = 2; i * i <= end; i++) {
        if (isPrime[i]) {
            for (int j = i * i; j <= end; j += i) {
                isPrime[j] = false;
            }
        }
    }
    for (int i = start; i <= end; i++) {
        if (isPrime[i]) {
            cout << i << " ";
        }
    }
    cout << endl;
}

int main() {
    int start = 10, end = 50;
    sievePrimes(start, end);
    return 0;
}

方法三：优化版筛法（欧拉筛/线性筛）

在埃氏筛基础上避免重复标记，时间复杂度更低（O(n)），但代码稍复杂。

#include <iostream>
#include <vector>
using namespace std;

void eulerSieve(int start, int end) {
    vector<bool> isPrime(end + 1, true);
    vector<int> primes;
    isPrime[0] = isPrime[1] = false;
    for (int i = 2; i <= end; i++) {
        if (isPrime[i]) primes.push_back(i);
        for (int p : primes) {
            if (i * p > end) break;
            isPrime[i * p] = false;
            if (i % p == 0) break;
        }
    }
    for (int i = start; i <= end; i++) {
        if (isPrime[i]) cout << i << " ";
    }
    cout << endl;
}

int main() {
    int start = 10, end = 50;
    eulerSieve(start, end);
    return 0;
}

方法四：分段筛法（处理极大区间）

当区间范围极大时（如1e12到1e12+1e6），结合埃氏筛和试除法分段处理。

// 示例代码较复杂，需根据具体需求实现

性能对比

• 试除法：适合小区间（如1e6以内），实现简单但效率低。
• 埃氏筛：适合中等区间（1e8以内），空间复杂度O(n)。
• 欧拉筛：适合需要频繁查询素数的情况，空间换时间。
• 分段筛：专用于超大区间，避免内存溢出。