algorithm - 在最短的时间内找到素数列表

Question

我阅读了很多算法来查找质数，并且得出的结论是，如果数不能被其前面的质数整除，那么该数就是质数。

我找不到更精确的定义。基于此，我编写了代码，直到通过的最大数为1000000为止，它的性能令人满意。但是，我相信有更快的算法可以找到小于给定数字的所有素数。

以下是我的代码，是否可以有一个更好的版本？

 public static void main(String[] args) {
    for (int i = 2; i < 100000; i++) {
        if (checkMod(i)) {
            primes.add(i);
        }
    }
}

private static boolean checkMod( int num) {
    for (int i : primes){
        if( num % i == 0){
            return false;
        }
    }
    return true;
}

Answer 1

素数测试的好处是，您只能除以素数。

private static boolean checkMod( int num) {
    for (int i : primes){
        if( num % i == 0){
            return false;
        }
    }
    return true;
}

不好的是，您将除以到目前为止找到的所有素数，即所有素数都小于候选数。这意味着，对于一百万以下的最大素数999983，用78497素数除以得出该数字是素数。这是很多工作。实际上，实际上，在算法达到质数时，花费到一百万时，约占所有工作的99.9％，对于更高的限制来说，这是很大的一部分。而且该算法几乎是二次方的，要以这种方式找到 n的素数，您需要执行

n² / (2*(log n)²)

师。

一个简单的改进是尽早停止 split 。令 n为一个复合数字(即除1之外的数字格数，除以1和 n以外的其他因数)，让 d为 n的除数。

现在， d是 n的除数意味着 n/d是整数，也是 n的除数: n/(n/d) = d。
因此，我们可以自然地将 n的除数分组为对，每个除数 d产生对 (d, n/d)。

对于这样的一对，有两种可能性:

d = n/d，表示n = d²或d = √n。

两者是不同的，所以其中一个小于另一个，例如d < n/d。但这会立即转换为d² < n或d < √n。

因此，无论哪种方式，每对除数都包含(至少)一个不超过 √n的值，因此， 如果n是一个复合数字，则其最小除数(除1外)不超过√n 。

因此，当我们到达 √n时，我们可以停止审判部门:

private static boolean checkMod( int num) {
    for (int i : primes){
        if (i*i > n){
            // We have not found a divisor less than √n, so it's a prime
            return true;
        }
        if( num % i == 0){
            return false;
        }
    }
    return true;
}

注意:这取决于按升序迭代的素数列表。如果语言无法保证，则必须使用其他方法，通过 ArrayList或类似方法按索引进行迭代。

停止对候选人的平方根进行试验除法，对于100万以下的最大素数999983，我们现在只需要将其除以1000以下的168个素数即可。这比以前要少得多的工作。在平方根处停止试除法，仅用质数除法，这和试除法可能获得并需要大约

2*n^1.5 / (3*(log n)²)

除数，对于 n = 1000000，大约是750的倍数，还不错吗？

但这仍然不是很有效，找到 n以下所有质数的最有效方法是筛子。简单实现是经典的 Sieve of Eratosthenes。这样可以在O(n * log log n)操作中找到 n以下的质数，并进行了一些增强(预先考虑了几个小质数的倍数)，可以将其复杂度降低为O(n)操作。一种比较新的具有更好渐近行为的筛子是 Sieve of Atkin，它在O(n)操作中找到 n的质数，或者在O(n/log log n)操作中增强了消除一些小质数的倍数的功能。
Atkin筛网的实现更为复杂，因此，良好的Eratosthenes筛网实现可能比朴素的Atkin筛网实现更好。对于类似优化级别的实现，除非限制变大(大于1010)，否则性能差异很小，并且在实践中，Eratatothenes筛网的扩展性优于Atkin筛网，这是由于更好的内存访问模式所致)。因此，我建议从Eratosthenes筛网开始，并且只有在尽管进行了真诚的优化工作却仍无法令人满意的情况下，才应深入研究Atkin筛网。或者，如果您不想自己实现它，请找到其他人已经认真调整过的好的实现。

我在 an answer中进行了更详细的介绍，设置略有不同，这里的问题是找到第n个素数。一些或多或少有效的方法的实现都与该答案相关联，尤其是Eratosthenes筛网的一种或两种可用(尽管优化程度不高)的实现。