c++ - 为什么这个 Sieve of Sundaram 实现比这个 Sieve of Eratosthenes 实现快得多？

Question

我目前正在尝试比较两种不同素数生成算法的平均运行速度。我有这个简单的埃拉托色尼筛法实现:

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

这就是我尝试衡量算法速度的方式。 test 是从命令行输入的参数。主程序会手动运行两次，第一次打印出sieve_of_eratosthenes的平均速度，第二次打印出sieve_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()

根据理论时间复杂度，Eratosthenes 筛法应该给出更快的结果(O(nlog(logn)) 比 O(nlogn) 快，这是Sundaram 筛法的时间复杂度)。然而，Sundaram 筛法实际上要快得多(几乎是 Eratosthenes 筛法的 3 倍)。

结果(以纳秒为单位):

434379
179904

Answer 1

您没有编写经典的 Sundaram 筛法(按 odds 筛选并且确实需要 O(N log N) 操作)，而是使用了一个小的修改(if (sieve[i]) ...) 这使得它等同于避免考虑偶数的埃拉托色尼筛法的一个版本。

由于您的其他代码使用了经典的埃拉托色尼筛法(按素数筛分)并且确实考虑了偶数，因此您所谓的 Sundaram 筛法代码确实快了一个常数因子。

这在 Wikipedia article on the Sieve of Sundaram 中有解释.