c++ - 更快地找到第 N 个素数的方法

Question

我最近试图在我的书中完成 100 个不同练习的列表，目前是第 23 个。找到第 N 个素数，虽然这看起来很容易，但我注意到搜索更大的素数需要很长时间数字(又名 50000 已经花费了大约 47 秒。

#include <iostream>
#include <time.h>

using namespace std;
bool checkPrime(int n);

int main()
{   
    while (true)
    {       
        register int number;
        cin >> number;
        register int counter = 0;
        register int numbers = 0;
        time_t start = clock();
        while (counter < number)
        {
            numbers++;
            if (checkPrime(numbers))counter++;
        }
        double time_diff = (clock() - start);
        cout << numbers << endl;
        cout << "Time needed to process in ms: " << time_diff << endl;
    }
}


bool checkPrime(int n) {
    if (n <= 1) return false;
    for (register int i = 2; i < n; i++) {
        if (n%i == 0)return false;
    }
    return true;
}

这就是代码本身，没有什么太花哨的，因为它仍然是更简单的练习之一，尝试将变量设置为寄存器，因为我听说它有时会让事情变得更快。 WolframAlpha 需要大约 10 秒来检查第 100.000 个素数，我这里的代码大约需要 90 秒。提前感谢 Folling

Answer 1

如果没有空间限制，请创建一个包含素数的 vector 并更改您的 checkPrime 方法，如下所示:

vector<int> primes;
bool checkPrime(int n) {
     if (n <= 1) return false;
     for (int i = 0; i < primes.size(), primes.at(i) <= sqrt(n); i++) {

          if (n%primes.at(i)== 0)
               return false;
     }
     primes.push_back(n)
     return true;
}

通过这种技术，您将仅检查 n 是否可以被素数整除，而不是检查直到其平方根的所有数字。

在这里，我们利用一个数字要么是素数，要么是一个或多个素数的倍数。

CheckPrime 方法的复杂度为 O(log n)，因此查找前 N 个素数的复杂度为 O(n log n)，其中 n 是第 N 个素数的值