为何我的C++实现的Atkin筛法质数搜索代码运行如此缓慢？

我对比了PHP/Lua/Python与C实现的Atkin筛法质数搜索算法性能，以C为基准，算法参考自Atkin筛法示例。四种语言都成功实现算法，并添加了输入搜索上限的交互循环（输入exit退出），测试结果如下：

测试结果 #

上限为1e6（共78498个质数） #

• Lua : ~0.18秒
• PHP : ~0.8秒
• Python3 : ~19秒

上限为1e5（共9592个质数） #

• C++ : ~12-13秒

C在上限低10倍的情况下性能远逊于Lua，这完全不符合预期——毕竟C本应比Lua快得多。我尝试过开启编译优化、用MS Visual Studio 2022（MSVC++20 ISO）编译、在笔记本和台式机（Ubuntu系统）上运行，甚至让亲友在他的机器上测试，结果始终一致：耗时约12-17秒（依机器而异）。

我究竟哪里做错了？

编译器选项与设备配置 #

• MinGW64/Win10及GNU GCC/Ubuntu：

  g++ -std=c++20 -march=x86-64 -mtune=ivybridge -O3 primenum.cpp -o primenum.exe
  

• MSVC20/Win10：Release模式，x64，ISO C20标准
• 台式机：Win10x64/Ubuntu server 24.04 LTS，Intel i5-3570K Ivy Bridge
• 笔记本：Win10x64，Intel i7-3537U Ivy Bridge

完整C++代码 #

#include <cmath>
#include <iostream>
#include <string>
using namespace std;
//=============================================================================
/* This C++ program generates all prime numbers (primes) up to
 * integer limit entered by user. Primes searching method implements Sieve
 * of Atkin algorithm.*/
//=============================================================================
// Convert string chars to lowercase
void str_tolower(string &str) {
    int length = str.length();
    for (int i = 0; i < length; ++i) {
        str[i] = (char)tolower(str[i]);
    }
}
// Sieve of Atkin algorithm main function
// ======================================
void SieveOfAtkin(size_t limit) {
    /* Initialise the sieve array with false values.
     * "2" and "3" are known to be prime.*/
    size_t length = limit + 1;
    size_t *sieve = new size_t[length]{};
    sieve[2] = 1;
    sieve[3] = 1;

    /* Mark sieve[n] is true if one of the following is true:
     * a) n = (4*x*x)+(y*y) has odd number of solutions, i.e., there exist
     * odd number of distinct pairs (x, y) that satisfy the equation and
     * n % 12 = 1 or n % 12 = 5.
     * b) n = (3*x*x)+(y*y) has odd number of solutions and n % 12 = 7
     * c) n = (3*x*x)-(y*y) has odd number of solutions, x > y and
     * n % 12 = 11.*/
    size_t n{}, x{}, y{};
    for (x = 0; x*x <= limit; ++x) {
        for (y = 0; y*y <= limit; ++y) {
            // (a)
            n = 4*x*x + y*y;
            if ((n <= limit) && (n % 12 == 1 || n % 12 == 5)) {
                sieve[n] = !sieve[n];
            }
            // (b)
            n = 3*x*x + y*y;
            if ((n <= limit) && (n % 12 == 7)) {
                sieve[n] = !sieve[n];
            }
            // (c)
            n = 3*x*x - y*y;
            if ((x > y) && (n <= limit) && (n % 12 == 11)) {
                sieve[n] = !sieve[n];
            }
        }
    }

    // Mark all multiples of squares as non-prime
    size_t r{}, i{};
    for (r = 5; r*r <= limit; ++r) {
        if (sieve[r]) {
            for (i = r*r; i <= limit; i += r*r) {
                sieve[i] = 0;
            }
        }
    }

    // Disable listing if 'limit' > 1086 (print only first 180 primes)
    bool disable_list_output = limit >= 1087 ? true : false;

    // Print primes using sieve[]
    size_t count{0};
    const unsigned char columns{20};

    for (size_t a = 2; a <= limit; ++a) {
        if (sieve[a]) {
            ++count;
            if (!disable_list_output) {
                cout.setf(ios::dec);
                cout.width(10);
                cout << a;
                if (count > 0 && count % columns == 0)
                    cout << endl;
            }
        }
    }

    delete[] sieve;
    if (disable_list_output) {
        cout << endl << "===========================================";
        cout << endl << "Primes count is over 180, listing disabled.";
    }

    cout << endl << "-------------------------------------------" << endl;
    cout << "Primes found: " << count << endl;
}

// Main loop of the program
// ========================
int main(void) {
    time_t start_time{};
    size_t limit{};
    string input{};
    float f_limit{};

    while (true) {
        // Read user input string
        cout << endl << "Enter positive integer, N > 3 : ";
        getline(cin, input);
        str_tolower(input);

        // Processing user input string
        // ----------------------------
        if (!cin or input.empty()) { // if input failed --> repeat 'while' loop
            continue;
        } else if (input == "exit") {
            // Successful program termination
            exit(EXIT_SUCCESS);
        } else {
            try { // if input is float --> OK...
                f_limit = stof(input);
            } catch (...) { // ...else --> repeat 'while' loop
                continue;
            }
            f_limit = stof(input);

            // Check if input is integer
            if (floor(f_limit) == f_limit) {
                limit = static_cast<size_t>(f_limit);
                start_time = time(NULL);
                SieveOfAtkin(limit);
                cout << "Execution time : " << time(NULL) - start_time << endl;
                cout << "===========================================" << endl;
            }
        }
    }
    return 0;
}

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