为什么这个 Sieve of Sundaram 实现比这个 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;
}

以及 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;
}

这就是我尝试测量算法速度的方式。 是从命令行输入的参数。主程序将手动运行 2 次，第一次将打印出 的平均速度，第二次将是 的平均速度。testsieve_of_eratosthenessieve_of_sundaram

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()

根据理论时间复杂度，埃拉托色尼筛子应该给出更快的结果（比 快，这是孙达拉姆筛子的时间复杂度）。然而，Sundaram 的筛子实际上要快得多（几乎是埃拉托色尼筛子的 3 倍）。O(nlog(logn))O(nlogn)

结果（以纳秒为单位）：

434379
179904