找到素数最快的算法是什么？

Question

哪个是使用 C++ 找出素数的最快算法？我已经使用了筛子的算法，但我仍然希望它更快！

原文由 kasperasky 发布，翻译遵循 CC BY-SA 4.0 许可协议

Answer 1

这是查找从 1 到 n 的所有素数的最快算法（在我的电脑上，它只用了 0.004 秒就找到了从 1 到 1000000 的所有素数）。

 #include <iostream>
#include <fstream>

using namespace std;

double FindPrime(bool* array, int size){
clock_t start;
double runtime;
for (int i = 2; i < size; i++)
    array[i] = true;
start = clock();
for (int i = 2; i <= size; i++)
    if (array[i])
        for (int j = 2 * i; j < size; j += i)
            array[j] = false;
runtime = (double)(clock() - start) / CLOCKS_PER_SEC;
return runtime;
}

int main() {
ofstream fout("prime.txt");
int n = 0;
cout << "Enter the upper limit of prime numbers searching algorithm:";
cin >> n;
bool* array = new bool[n + 1];
double duration = FindPrime(array, n + 1);
printf("\n%f seconds.\n", duration);
for (int i = 2; i <= n; i++)
    if (array[i])
        fout << i << endl;
fout.close();

return 0;
}

原文由 Rist 发布，翻译遵循 CC BY-SA 4.0 许可协议