为何Sieve of Sundaram实现比Sieve of Eratosthenes快近3倍？

我正在对比两种素数生成算法的平均运行速度，分别实现了朴素版Sieve of Eratosthenes（埃拉托斯特尼筛法）与Sieve of Sundaram（Sundaram筛法）。理论上埃氏筛的时间复杂度O(nlog(logn))优于Sundaram筛的O(nlogn)，但实测结果显示Sieve of Sundaram快近3倍（运行时间分别为434379纳秒、179904纳秒），想了解这一现象的原因。

算法实现代码 #

Sieve of Eratosthenes 实现 #

std::vector<int32_t> sieve_of_eratosthenes(int32_t n) {
    std::vector<int32_t> primes;
    std::vector<bool> sieve(n + 1, true);
    for (int32_t i = 2; i * i <= n; i++) {
        if (sieve[i]) {
            for (int j = i * i; j <= n; j += i) {
                sieve[j] = false;
            }
        }
    }
    for (int32_t i = 2; i < n; ++i) {
        if (sieve[i]) primes.push_back(i);
    }
    return primes;
}

Sieve of Sundaram 实现 #

std::vector<int32_t> sieve_of_sundaram(int32_t n) {
    std::vector<int32_t> primes;
    int32_t k = (n - 1) / 2;
    std::vector<bool> sieve(k + 1, true);
    for (int32_t i = 1; i * i <= k; ++i) {
        if (sieve[i]) {
            for (int32_t j = i; i + j + 2 * i * j <= k; ++j) {
                sieve[i + j + 2 * i * j] = false;
            }
        }
    }
    if (n > 2) primes.push_back(2);
    for (int32_t i = 1; i <= k; ++i) {
        if(sieve[i]) primes.push_back(2 * i + 1);
    }
    return primes;
}

测试方法代码 #

std::vector<int32_t> test_input(1000, 100000);
std::vector<int32_t> result;
switch (test) {
    case 1:
        for (auto n : test_input) {
            auto start = std::chrono::high_resolution_clock::now();
            auto tmp = sieve_of_eratosthenes(n);
            auto end = std::chrono::high_resolution_clock::now();
            int32_t runtime = std::chrono::duration_cast<std::chrono::nanoseconds>(end - start).count();
            result.push_back(runtime);
        }
        break;
    case 2:
        for (auto n : test_input) {
            auto start = std::chrono::high_resolution_clock::now();
            auto tmp = sieve_of_sundaram(n);
            auto end = std::chrono::high_resolution_clock::now();
            int32_t runtime = std::chrono::duration_cast<std::chrono::nanoseconds>(endd - start).count();
            result.push_back(runtime);
        }
        break;
    default:
        break;
}
std::cout << get_avg(result); // sum of all test results / result.size()

性能差异的原因分析 #

• 内存缓存效率更高：
  埃氏筛的筛数组大小为n+1（n=1e5时是100001个bool元素），而Sundaram筛的筛数组仅为(n-1)/2（约50000个元素）。更小的数组能更好地适配CPU缓存，减少缓存缺失带来的内存访问延迟，这是性能差异的核心原因之一。

• 标记操作总量更少：
  Sundaram筛通过数学公式直接跳过了所有偶数的处理，只需要标记奇数对应的合数；而埃氏筛需要标记所有偶数和奇数的合数，实际执行的标记操作次数更少，循环迭代的总开销更低。

• 循环内存访问模式更优：
  埃氏筛在处理小素数（比如i=2）时，会连续访问大量分散的内存地址（所有偶数位置），容易导致缓存行频繁失效；而Sundaram筛的标记操作对应的内存位置分布更紧凑，缓存命中率更高，单次内存访问的有效利用率更好。

• 编译器优化的影响：
  若测试时开启了O2/O3级别的编译器优化，Sundaram筛更紧凑的代码结构和内存布局更容易被编译器做循环展开、指令重排等优化，进一步放大性能优势。另外注意测试代码中Sundaram筛部分有笔误endd，实际运行时应该已经修正，否则无法编译。

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