8

我读了很多算法来找到素数，结论是如果一个数字不能被它前面的任何一个素数整除，那么它就是一个素数。

我找不到更准确的定义。基于此，我编写了一个代码，它的性能令人满意，直到我通过的最大数字为 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;
}
4

7 回答 7

21

素数测试的好处是你只除以素数。

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

坏事是你除以目前找到的所有素数，即所有小于候选的素数。这意味着对于低于 100 万的最大素数 999983，您除以 78497 个素数以发现这个数字是素数。这是很多工作。事实上，当达到 100 万时，在这个算法中花费在素数上的工作占所有工作的 99.9% 左右，在更高的限制中占比更大。而且该算法几乎是二次的，要n以这种方式找到素数，您需要执行大约

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

师。

一个简单的改进是提前停止除法。令n为合数（即大于 1 且除数不是 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² < nor 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;
}

注意：这取决于按升序迭代的素数列表。如果语言不能保证这一点，则必须使用不同的方法，通过索引迭代 anArrayList或类似的东西。

在候选的平方根处停止试除法，对于 100 万以下的最大素数 999983，我们现在只需将其除以 1000 以下的 168 个素数。这比以前少了很多工作。在平方根处停止试除法，并且只除以素数，与试除法一样好，并且需要大约

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

师，因为n = 1000000，这是一个大约 750 的因素，还不错，是吗？

但这仍然不是很有效，找到下面所有素数的最有效方法n是筛子。实施简单的是经典的埃拉托色尼筛法。在 O(n*log log n) 操作中找到下面的素数n，通过一些增强（预先排除几个小素数的倍数），它的复杂性可以降低到 O(n) 操作。一种具有更好渐近行为的相对较新的筛子是阿特金筛子，它找到了n在 O(n) 操作中，或者在 O(n/log log n) 操作中消除一些小素数的倍数的增强。阿特金筛子的实现更复杂，因此埃拉托色尼筛子的良好实现可能比阿特金筛子的简单实现表现更好。对于类似优化级别的实现，性能差异很小，除非限制变大（大于 10 10; 并且在实践中，由于更好的内存访问模式，Eratosthenes 的 Sieve 比 Atkin 的 Sieve 具有更好的扩展性并不少见）。因此，我建议从 Eratosthenes 筛开始，并且仅当尽管诚实地优化优化但其性能仍不能令人满意时，才深入研究 Atkin 筛。或者，如果您不想自己实现它，请找到其他人已经认真调整过的良好实现。

我在一个稍微不同的设置的答案中进行了更详细的介绍，问题是找到第 n 个素数。或多或少有效方法的一些实现与该答案相关联，特别是 Eratosthenes 筛的一个或两个可用（尽管没有多少优化）实现。

于 2012-05-21T22:01:26.740 回答
1

我总是使用 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

希望你能理解我的评论

于 2012-05-21T18:58:58.233 回答
0

我理解素数是一个只能被自身和数字 1 整除的数字（没有余数）。见维基百科文章

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

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

这是基于这样的假设：1、2 和 3 都是素数，之后的所有偶数都不是素数。这至少将您的算法减半。

于 2012-05-21T19:01:07.903 回答
0

我想对上面 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的所有因素并提高。

于 2014-02-02T06:46:55.817 回答
0

@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;
}
于 2014-03-30T17:01:02.330 回答
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
于 2020-03-15T17:01:41.243 回答
0

我发现数学家说“那”“3 之后的质数总是 6 的倍数的一侧”。5 ,7 素数更接近 6。11,13 也更接近 6 2。17,19 也接近 6 3。21,23也接近6*4。我写的都很正常，像这样最多100万，我发现这个算法也对，而且速度更快。

num=1000000
prime=[2,3]
def test(i):
    for j in prime:
        if(i%j==0):
            break
        if(j*j>i):
            prime.append(i)
            break
    return 0
for i in range (6,num,6):
    i=i-1
    test(i)
    i=i+2
    test(i)
    i=i-1
    
print(prime)
于 2020-07-12T03:47:41.483 回答