algorithm - 计算一百万个素数

Question

我有一个问题要打印一百万个素数。我为此编写了一个 java 程序。目前计算它大约需要 1.5 分钟。我认为我的解决方案效率不高。我使用了以下算法：

最初将 1 2 3 添加到素数列表
计算要检查的数字的最后一位
检查数字是否为 0 、 2 或 4 或 6 或 8 然后跳过数字
否则计算数字的平方根..
试图将数字从 2 开始除以数字的平方根
如果数字可整除，则跳过数字，否则将其添加到素数列表

我也阅读了其他几个解决方案，但我没有找到一个好的答案。理想情况下，请建议计算此时间的最短时间以及需要进行哪些更改才能使算法更有效。

score 15 · Accepted Answer

如果您在列表中添加了 1，那么您的答案已经错了 :)

无论如何，埃拉托色尼筛法是您应该开始的地方，它非常简单且非常有效。

一旦您熟悉了筛子的概念以及它们的工作原理，您就可以继续使用Sieve of Atkin，它有点复杂，但显然更有效。

score 5 · Accepted Answer

关键事项：

跳过所有偶数。从 5 开始，一次添加两个。
1不是质数...
通过找到所有素数的模直到数字的平方根来测试一个数字。除了素数之外，无需测试任何东西。

score 3 · Accepted Answer

您可能希望实现埃拉托色尼筛算法以查找从 1 到的素数，n并在需要时迭代地增加范围。（即尚未找到 1,000,000 个素数）

score 3 · Accepted Answer

一个简单的 Eratosthenes 筛子像拍板一样运行。这会在不到一秒的时间内计算出我的盒子上的第 1,000,000 个素数：

class PrimeSieve
{
    public List<int> Primes;

    private BitArray Sieve;

    public PrimeSieve(int max)
    {
        Primes = new List<int> { 2, 3 }; // Must include at least 2, 3.
        Sieve = new BitArray(max + 1);
        foreach (var p in Primes)
            for (var i = p * p; i < Sieve.Length; i += p) Sieve[i] = true;
    }

    public int Extend()
    {
        var p = Primes.Last() + 2; // Skip the even numbers.
        while (Sieve[p]) p += 2;
        for (var i = p * p; i < Sieve.Length; i += p) Sieve[i] = true;
        Primes.Add(p);
        return p;
    }
}

编辑：最佳筛选从 p^2 开始，而不是 2p，正如 Will Ness 正确指出的那样（所有低于 p^2 的化合物数都将在早期迭代中标记）。

score 3 · Accepted Answer

首先，1 不是质数。

其次，第 100 万个素数是 15,485,863，因此您需要为一些大型数据处理做好准备。

第三，您可能想使用埃拉托色尼筛；这是一个简单的版本：

function sieve(n)
    bits := makeArray(0..n, True)
    for p from 2 to n step 1
        if bits[p]
            output p
            for i from p*p to n step p
                bits[i] := False

这可能不适用于计算前一百万个素数所需的数组大小。在这种情况下，您将需要实现 Eratosthenes 的分段筛。

我在博客中对质数做了很多工作，包括一篇提供优化的埃拉托色尼筛法的文章，并以五种编程语言实现。

无论您做什么，使用任何编程语言，您都应该能够在不超过几秒钟的时间内计算出前一百万个素数。

score 1 · Accepted Answer

这是一个实现Trial 除法筛的 Ocaml 程序（Will 正确指出，这是 Eratosthenes 的倒数）：

(* Creates a function for streaming integers from x onward *)
let stream x =
  let counter = ref (x) in
  fun () ->
    let _ = counter := !counter + 1 in
    !counter;;

(* Filter the given stream of any multiples of x *)
let filter s x = fun () ->
  let rec filter' () = match s () with
    n when n mod x = 0 ->
      filter' ()|
    n ->
      n in
  filter' ();;

(* Get next prime, apply a new filter by that prime to the remainder of the stream *)
let primes count =
  let rec primes' count' s = match count' with
    0 ->
      []|
    _ -> 
      let n = s () in
      n :: primes' (count' - 1) (filter s n) in
  primes' count (stream 1);;

它适用于整数流。每次发现一个新的素数时，都会向流中添加一个过滤器，以便将流的其余部分过滤掉该素数的任何倍数。该程序也可以更改为按需生成素数。

在 Java 中采用相同的方法应该相当容易。

希望这可以帮助！

score 1 · Accepted Answer

这是一个 javascript 解决方案，它使用递归和迭代来达到百万分之一的素数。它不如埃拉托色尼筛法快，但不需要事先知道第百万个素数的值（即所需筛子的大小）：

function findPrimes(n, current, primes) {
    if (!n || current < 2) return []
    var isPrime = true
    for (var i = 0; i < primes.length; i++) {
        if (current % primes[i] == 0) {
            isPrime = false
            break
        }
    }
    if (isPrime) primes.push(current)
    if (primes.length < n) return findPrimes(n, current + 1, primes)
    else return primes
}

var primes = [2,3]
for (var i = 1; i <= 1000; i++) {
    primes = findPrimes(i*1000, primes[primes.length - 1]+1, primes)
    console.log(i*1000 + 'th prime: ' + primes[primes.length-1])
}
process.exit()

输出：

...
996000th prime: 15419293
997000th prime: 15435941
998000th prime: 15452873
999000th prime: 15469313
1000000th prime: 15485863

Process finished with exit code 0

score 1 · Accepted Answer

作为一个较新的级别，我将尝试这个级别，因此任何提高效率和速度的改进都值得赞赏

 public static void main(String ar[]) {
    ArrayList primeNumbers = new ArrayList();

    for(int i = 2; primeNumbers.size() < 1000000; i++) {//first 1 million prime number

       // for(int i = 2; i < 1000000; i++) {//prime numbers from 1 to 1 million

            boolean divisible = false;

        for(int j=2;j<i/2;j++){

            if((i % j) == 0) {
                divisible = true;
                break;
            }
        }

        if(divisible == false) {
            primeNumbers.add(i);
           // System.out.println(i + " ");
        }
    }
    System.out.println(primeNumbers);
}

score 1 · Accepted Answer

最初将 1 2 3 添加到素数列表

实际上，只需 2 个就足够了。硬编码 3 最多可以节省一毫秒。没有必要在 1 上竖琴。我相信包括它是一个诚实的错误。你已经知道了，并且在这个程序上工作将有助于证实这一点。

计算要检查的数字的最后一位

最后一个数字？在什么基地？基数 10？我想这可能是你的问题。

检查数字是否为 0、2 或 4 或 6 或 8，然后跳过数字，否则计算数字的平方根

我认为这就是问题所在。您的程序应该简单地跳过偶数，因为除了 -2 和 2 之外，它们都是复合的。另一方面，这不会将运行时间减半，因为像 91 和 2209 这样的奇数可能需要更多的努力才能被排除为非质数。

尝试将数字从 2 开始除以数字的平方根，如果数字是可整除的，则跳过数字，否则将其添加到素数列表

“2 直到数字的平方根”是否包括像 4、6 和 9 这样的数字？唯一需要检查的潜在因素是已经被证明是素数的数字。如果n不能被 7 整除，则它也不能被 49 整除。如果你正在建立一个列表，你不妨用它来检查潜在的素数。

对 Java 进行基准测试有点困难，因为您受制于运行时系统。尽管如此，一分半钟虽然被梅森认为是奇迹，但在今天还是太慢了。五，十秒，我觉得可以接受。

也许这是您应该避免使用对象来支持原语数组的情况之一。我的初稿比你的还要长。最终我想出了这个：

    static int[] fillWithPrimes(int quantity) {
        int[] primes = new int[quantity];
        primes[0] = 2;
        int currPi = 1;
        int currIndex = 0;
        int currNum = 3;
        int currPrime;
        boolean coPrimeFlag;
        double squareRoot;
        while (currPi < quantity) {
            squareRoot = Math.sqrt(currNum);
            do {
                currPrime = primes[currIndex];
                coPrimeFlag = (currNum % currPrime != 0);
                currIndex++;
            } while (coPrimeFlag && currPrime <= squareRoot);
            if (coPrimeFlag) {
                primes[currPi] = currNum;
                currPi++;
            }
            currNum += 2;
            currIndex = 0;
        }
        return primes;
    }

然后我写了一个main()记录调用前的时间，fillWithPrimes()参数quantity为 1,000,000，并报告结果：

跑：

操作耗时 2378 毫秒

第 10 个素数是 29

第 100 个素数是 541

第 1000 个素数是 7919

第 10000 个素数是 104729

第 100000 个素数是 1299709

第 1000000 个素数是 15485863

构建成功（总时间：2 秒）

我相信它可以进一步优化。就我个人而言，我对两秒半的时间感到满意。

score -1 · Accepted Answer

不是 5 之后的所有内容都以 5 结尾，也可以被 5 整除，因此您可以跳过正确的内容 (1,numb)<>"5" 例如 987,985。我在 Excel 中制作了一个，它将测试一百万个素数并在大约 15 秒内将它们吐到一列中，但它会在大约 1500 万个时变得疯狂

algorithm - 计算一百万个素数

10 回答 10

Related

Reference