C++中埃拉托斯特尼筛法的效率优化问题（面向C++完全初学者）

嘿，作为C++初学者能写出埃氏筛的实现已经很赞了！你猜的没错——把塞满大量0的向量直接转unordered_set确实是效率瓶颈之一，除此之外还有几个关键的优化点，咱们一步步来改进：

核心优化点 #

1. 用标记数组替代全量数值存储，减少内存开销 #

你原来的做法是用vector<int>存储0到max_val的所有数，筛完后把非素数设为0，这不仅占用大量内存（1000万的int向量要40MB左右），后续处理大量0也非常耗时。改用**vector<bool>做素数标记**会高效很多：它是位压缩存储的，1000万只需要约1.2MB内存，缓存命中率更高，读写速度更快。

2. 缩小筛法的循环上限 #

原来的循环跑了从2到max_val的所有数，但实际上只需要循环到sqrt(max_val)就够了：如果一个数n有大于sqrt(n)的因子，那对应的另一个因子必然小于sqrt(n)，已经被之前的素数筛过了。比如1000万的平方根约为3162，循环次数直接从1000万降到3000多，效率提升非常明显。

3. 跳过已被筛过的倍数，减少重复操作 #

筛素数i的倍数时，不需要从2i开始——因为更小的倍数（比如i2、i*3...）已经被比i小的素数筛过了，直接从i*i开始筛就行，进一步减少无效操作。

4. 直接收集有效素数，避免处理大量无效值 #

不用先存全量再转集合，筛完后直接遍历标记数组，把素数收集到列表里（或者直接计数），完全跳过非素数的0，避免了unordered_set插入大量无效元素的开销——这也是你之前Python程序更快的关键原因之一，Python的筛法应该是直接收集有效素数的。

5. 预分配内存，避免频繁扩容 #

如果需要存储素数列表，可以根据素数定理（小于n的素数个数约为n/ln(n)）预分配内存，避免vector在插入过程中频繁扩容拷贝，提升效率。

优化后的完整代码 #

#include <iostream>
#include <vector>
#include <chrono>
#include <cmath>

int main() {
    auto start = std::chrono::high_resolution_clock::now();
    const int max_val = 10000000; // 1000万
    
    // 用vector<bool>做素数标记，内存占用极小
    std::vector<bool> is_prime(max_val + 1, true);
    is_prime[0] = is_prime[1] = false; // 0和1不是素数
    
    // 循环上限优化到sqrt(max_val)
    const int sqrt_max = static_cast<int>(std::sqrt(max_val));
    for (int i = 2; i <= sqrt_max; ++i) {
        if (is_prime[i]) { // 只有当i是素数时，才筛它的倍数
            // 从i*i开始筛，更小的倍数已被之前的素数处理
            for (int j = i * i; j <= max_val; j += i) {
                is_prime[j] = false;
            }
        }
    }
    
    // 统计素数数量，同时收集素数列表（如果需要）
    int prime_count = 0;
    std::vector<int> primes_list;
    // 预分配内存，根据素数定理估算素数数量
    primes_list.reserve(static_cast<size_t>(max_val / std::log(max_val)));
    
    for (int i = 2; i <= max_val; ++i) {
        if (is_prime[i]) {
            prime_count++;
            primes_list.push_back(i);
        }
    }
    
    std::cout << "素数数量：" << prime_count << "\n";
    auto stop = std::chrono::high_resolution_clock::now();
    auto duration = std::chrono::duration_cast<std::chrono::milliseconds>(stop - start);
    std::cout << "耗时：" << duration.count() << " ms\n";
    
    return 0;
}

额外提示 #

• 如果不需要存储素数列表，只需要统计数量，可以直接去掉primes_list相关代码，速度还能再提一截。
• unordered_set在这里完全没必要：如果需要判断某个数是否是素数，直接用is_prime数组查询就行（O(1)时间）；如果需要遍历素数，vector的遍历效率也远高于unordered_set。

试试这些优化，你会发现C++版本的速度会轻松超过Python的~

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