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

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;
}

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

n² / (2*(log n)²)
部门。

一个简单的改进是尽早停止分裂。令n为一个合成数（即除1之外的数字格，除以n以外的其他因子），令d为n的一个因数。

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

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

1. [d = n/d，表示n = d²或d = √n。
2. 两者是不同的，所以其中一个小于另一个，例如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筛网实现更好。对于类似优化级别的实现，除非限制变大（大于10 [10]），否则性能差异很小；而且在实践中，Eratatothenes筛网的缩放效果要比Atkin筛网的伸缩性更好，这是不常见的更好的内存访问模式）。因此，我建议您从Eratosthenes筛网开始，并且只有在尽管经过认真努力进行优化后其性能仍不能令人满意时，才应深入研究Atkin筛网。或者，如果您不想自己实施，则可以找到已经有人认真调整过的良好实施。

^{我在an answer中有一个稍微不同的设置，它的问题在于找到第n个素数。一些或多或少有效的方法的实现都与该答案相关联，尤其是Eratosthenes筛网的一种或两种可用（尽管优化程度不高）的实现。}

我总是使用Eratosthenes筛子：

isPrime[100001] // - initially contains only '1' values (1,1,1 ... 1)
isPrime[0] = isPrime[1] = 0 // 0 and 1 are not prime numbers

primes.push(2); //first prime number. 2 is a special prime number because is the only even prime number.
for (i = 2; i * 2 <= 100000; i++) isPrime[i * 2] = 0 // remove all multiples of 2

for (i = 3; i <= 100000; i += 2) // check all odd numbers from 2 to 100000
    if (isPrime[i]) {
        primes.push(i); // add the new prime number to the solution
        for (j = 2; i * j <= 100000; j++) isPrime[i * j] = 0; // remove all i's multiples
    }

return primes

希望您能理解我的评论

我知道素数是一个只能被其自身和数字1（无余数）整除的数字。参见Wikipedia Article

话虽如此，我在第二条评论中对算法不是很了解，但是对算法的一个小改进是将for循环更改为：

for (int i = 5; i < 100000; i = i + 2) {
    if (checkMod(i)) {
        primes.add(i);
    }
}

这是基于以下假设：1、2和3均为素数，此后所有偶数均不是素数。这至少可以将您的算法减少一半。

我想对上面的本杰明·阿曼（Benjamin Oman）建议的0ne做一个稍微改进的版本，这只是避免对所有以数字'5'结尾的数字进行素数检查的一种修改，因为这些数字肯定不是质数，因为它们可以被5整除。

for (int i = 7;(i < 100000) && (!i%5==0); i = i + 2) {
    if (checkMod(i)) {
        primes.add(i);
    }
}

这是基于2,3,5是质数的假设。上述微小变化将减少5的所有因子并改善。

@Daniel Fischer很好地解释。

他解释中的C ++实现：

#include<iostream>

using namespace std;

long* getListOfPrimeNumbers (long total)
{
  long * primes;
  primes = new long[total];
  int count = 1;
  primes[0] = 2;
  primes[1] = 3;
  while (count < total)
  {
    long composite_number = primes[count] + 2;
    bool is_prime = false;
    while (is_prime == false)
    {
      is_prime = true;
      for (int i = 0; i <= count; i++)
      {
        long prime = primes[i];
        if (prime * prime > composite_number)
        {
          break;
        }
        if (composite_number % prime == 0)
        {
          is_prime = false;
          break;
      }
      }
      if (is_prime == true)
      {
        count++;
        primes[count] = composite_number;
      }
      else
      {
        composite_number += 2;
    }
  }
  }
  return primes;
}

int main()
{
  long * primes;
  int total = 10;
  primes = getListOfPrimeNumbers(total);
  for (int i = 0; i < total; i++){
    cout << primes[i] << "\n";
  }
  return 0;
}

import array , math

print("enter a range to find prime numbers")

a= 0
b= 5000
c=0
x=0
k=1
g=[2]
l=0


for I in range( a , b):
    for k in g:
        x=x+1


        if k>2:
            if k > math . sqrt( I ):

                break

        if( I % k==0):

            c=c+1
            break
    if c==0:
        if I!=1:

            g . append( I )



    c=0    
print g



#this algorithm will take only 19600 iteration for a range from 1-5000,which is one of fastest algorithm according to me

Answer 2

我总是使用Eratosthenes筛子：

isPrime[100001] // - initially contains only '1' values (1,1,1 ... 1)
isPrime[0] = isPrime[1] = 0 // 0 and 1 are not prime numbers

primes.push(2); //first prime number. 2 is a special prime number because is the only even prime number.
for (i = 2; i * 2 <= 100000; i++) isPrime[i * 2] = 0 // remove all multiples of 2

for (i = 3; i <= 100000; i += 2) // check all odd numbers from 2 to 100000
    if (isPrime[i]) {
        primes.push(i); // add the new prime number to the solution
        for (j = 2; i * j <= 100000; j++) isPrime[i * j] = 0; // remove all i's multiples
    }

return primes

Answer 3

我知道素数是一个只能被其自身和数字1（无余数）整除的数字。参见Wikipedia Article

话虽如此，我在第二条评论中对算法不是很了解，但是对算法的一个小改进是将for循环更改为：

Answer 4

我想对上面的本杰明·阿曼（Benjamin Oman）建议的0ne做一个稍微改进的版本，这只是避免对所有以数字'5'结尾的数字进行素数检查的一种修改，因为这些数字肯定不是质数，因为它们可以被5整除。

for (int i = 7;(i < 100000) && (!i%5==0); i = i + 2) {
    if (checkMod(i)) {
        primes.add(i);
    }
}

Answer 5

@Daniel Fischer很好地解释。

他解释中的C ++实现：

Answer 6

import array , math

print("enter a range to find prime numbers")

a= 0
b= 5000
c=0
x=0
k=1
g=[2]
l=0


for I in range( a , b):
    for k in g:
        x=x+1


        if k>2:
            if k > math . sqrt( I ):

                break

        if( I % k==0):

            c=c+1
            break
    if c==0:
        if I!=1:

            g . append( I )



    c=0    
print g



#this algorithm will take only 19600 iteration for a range from 1-5000,which is one of fastest algorithm according to me