c++ - 找到范围内素数的最快方法是什么？

Question

我有这段代码可以找到素数:

void writePrimesToFile(int begin, int end, ofstream& file)
{
bool isPrime = 0;
for (int i = begin; i < end; i = i+2)
{
    isPrime = 1;
    for (int j = 2; j<i; j++)
        if (i % j == 0)
        {
            isPrime = 0;
            break;
        }
    if (isPrime)
        file << i << " \n";
}
}

有没有更快的方法呢？我尝试使用谷歌搜索更快的方法，但这全是数学，我不明白如何将其转化为代码。

Answer 1

Is there a faster way to do it?

是的。有更快的素性测试算法。

What is fastest way to find a prime number in range?

没有人知道。如果有人知道，那么这个人就是在保守一个非常重要的 secret 。没有人能够证明任何已知技术是测试素性的最快方法。

---

您可能会问:已知最快的找到范围内素数的方法是什么。

答案是:视情况而定。一些算法的复杂性比其他算法的复杂性渐进地增长得慢，但如果输入数字很小，那是无关紧要的。有些概率方法对于某些数字来说非常快，但在有问题的情况下它们比确定性方法慢。

您输入的数字很小，因为它们是 int 类型，因此范围非常有限。对于小数字，简单的算法可能比更复杂的算法更快。要找出最适合您的用例的算法，您必须对它们进行基准测试。

我建议从 Sieve of Eratosthenes 开始因为它比您的天真方法渐进地快，而且易于实现(维基百科提供的伪代码):

Input: an integer n > 1

 Let A be an array of Boolean values, indexed by integers 2 to n,
 initially all set to true.

 for i = 2, 3, 4, ..., not exceeding √n:
   if A[i] is true:
     for j = i², i²+i, i²+2i, i²+3i, ..., not exceeding n :
       A[j] := false

 Output: all i such that A[i] is true.