C++初学者求助：埃拉托斯特尼筛法有问题的实现代码排查

我来帮你梳理这段代码里的问题，然后给出完整的修正方案：

现有代码的核心问题 #

• 核心筛法逻辑缺失：你处理了min=1的情况后没有后续代码，整个埃拉托斯特尼筛法的核心质数标记过程完全没实现
• 边界条件覆盖不全：没有处理min > max的极端情况，这种情况下应该直接返回空结果
• 筛法范围处理思路未落地：常规埃氏筛需要先构建[2, max]的质数标记集合，再从中筛选出符合min要求的质数，你的代码还没走到这一步

修正后的完整代码 #

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

vector<unsigned long long int> sieveOfEratosthenes(unsigned long long int min, unsigned long long int max) {
    vector<unsigned long long int> result;
    
    // 统一处理边界异常情况
    if (max <= 1 || min > max) {
        return result;
    }
    if (min < 2) {
        min = 2; // 1不是质数，直接将起始筛选点设为2
    }

    // 创建质数标记数组：isPrime[i]表示数字i是否为质数，初始默认全为true
    vector<bool> isPrime(max + 1, true);
    isPrime[0] = isPrime[1] = false; // 0和1明确不是质数

    // 埃拉托斯特尼筛法核心逻辑
    for (unsigned long long int p = 2; p * p <= max; ++p) {
        if (isPrime[p]) { // 如果当前数是质数，标记它的所有倍数为非质数
            // 从p*p开始标记，因为更小的倍数已经被更小的质数标记过了，提升效率
            for (unsigned long long int multiple = p * p; multiple <= max; multiple += p) {
                isPrime[multiple] = false;
            }
        }
    }

    // 收集[min, max]范围内的所有质数
    for (unsigned long long int num = min; num <= max; ++num) {
        if (isPrime[num]) {
            result.push_back(num);
        }
    }

    return result;
}

// 测试用例
int main() {
    clock_t start = clock();
    vector<unsigned long long int> primes = sieveOfEratosthenes(1, 100);
    clock_t end = clock();

    cout << "Primes between 1 and 100:\n";
    for (unsigned long long int p : primes) {
        cout << p << " ";
    }
    cout << "\nTime taken: " << (double)(end - start)/CLOCKS_PER_SEC << " seconds\n";

    return 0;
}

关键细节说明 #

• 边界处理：先把所有异常情况（比如范围无效、包含非质数起始点）提前处理，避免后续逻辑出错
• 内存优化：用bool类型数组做标记，比用int数组节省大量内存空间
• 效率优化：标记倍数时从p*p开始，而不是2*p，因为更小的倍数已经被之前的质数标记过了
• 结果收集：遍历标记数组，精准提取[min, max]区间内的质数，确保结果符合需求

内容的提问来源于stack exchange，提问作者user2650277