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

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

这是我尝试测量算法速度的方法。test是从命令行输入的参数。主程序将手动运行2次，第一次将打印出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()

根据理论上的时间复杂度，埃拉托色尼筛应该给予更快的结果（O(nlog(logn))比O(nlogn)快，这是孙达兰筛的时间复杂度）。然而，孙达兰筛实际上快得多（几乎是埃拉托色尼筛的3倍）。
结果（以纳秒为单位测量）：

434379
179904