用 Eratosthenes 筛法寻找素数(原文:有没有更好的方法来准备这个数组?)

问题描述

注意:下面的第 2 版使用 Eratosthenes 筛.有几个答案对我最初提出的问题有所帮助.我选择了 Eratosthenes 筛法，实施了它，并适当地更改了问题标题和标签.感谢所有帮助过的人！

Note: Version 2, below, uses the Sieve of Eratosthenes. There are several answers that helped with what I originally asked. I have chosen the Sieve of Eratosthenes method, implemented it, and changed the question title and tags appropriately. Thanks to everyone who helped!

我编写了这个奇特的小方法，它生成一个 int 数组，其中包含小于指定上限的素数.效果很好，但我有一个顾虑.

I wrote this fancy little method that generates an array of int containing the prime numbers less than the specified upper bound. It works very well, but I have a concern.

private static int [] generatePrimes(int max) {
    int [] temp = new int [max];
    temp [0] = 2;
    int index = 1;
    int prime = 1;
    boolean isPrime = false;
    while((prime += 2) <= max) {
        isPrime = true;
        for(int i = 0; i < index; i++) {
            if(prime % temp [i] == 0) {
                isPrime = false;
                break;
            }
        }
        if(isPrime) {
            temp [index++] = prime;
        }
    }
    int [] primes = new int [index];
    while(--index >= 0) {
        primes [index] = temp [index];
    }
    return primes;
}

我的担忧

我担心的是，我创建的数组对于该方法将返回的最终元素数量来说太大了.问题是不知道有什么好的方法可以正确猜出小于指定数的素数个数.

My Concern

My concern is that I am creating an array that is far too large for the final number of elements the method will return. The trouble is that I don't know of a good way to correctly guess the number of prime numbers less than a specified number.

这就是程序使用数组的方式.这就是我想要改进的地方.

This is how the program uses the arrays. This is what I want to improve upon.

1. 我创建了一个临时数组，它是大到足以容纳每个数字小于限制.
2. 我生成素数，而计算我有多少生成.
3. 我创建了一个正确的新数组仅容纳素数的维度数字.
4. 我从巨大的数组到数组正确的尺寸.
5. 我返回正确的数组只保存素数的维度我生成的数字.

问题

1. 我可以(一次)复制整个块temp[] 具有非零值素数[]的元素无需迭代两个数组并复制元素一个一个?
2. 是否有任何数据结构表现得像一组原语可以随着元素的添加而增长，而不是需要一个维度在实例化时?是什么性能损失相比使用一组原语?

1. Can I copy the whole chunk (at once) oftemp[] that has nonzeroelements to primes[]without having to iterate throughboth arrays and copy the elementsone by one?
2. Are there any data structures thatbehave like an array of primitivesthat can grow as elements are added,rather than requiring a dimensionupon instantiation? What is theperformance penalty compared tousing an array of primitives?

版本 2(感谢 Jon Skeet):

private static int [] generatePrimes(int max) {
    int [] temp = new int [max];
    temp [0] = 2;
    int index = 1;
    int prime = 1;
    boolean isPrime = false;
    while((prime += 2) <= max) {
        isPrime = true;
        for(int i = 0; i < index; i++) {
            if(prime % temp [i] == 0) {
                isPrime = false;
                break;
            }
        }
        if(isPrime) {
            temp [index++] = prime;
        }
    }
    return Arrays.copyOfRange(temp, 0, index);
}

版本 3(感谢 Paul Tomblin)使用 埃拉斯托色尼筛网:

private static int [] generatePrimes(int max) {
    boolean[] isComposite = new boolean[max + 1];
    for (int i = 2; i * i <= max; i++) {
        if (!isComposite [i]) {
            for (int j = i; i * j <= max; j++) {
                isComposite [i*j] = true;
            }
        }
    }
    int numPrimes = 0;
    for (int i = 2; i <= max; i++) {
        if (!isComposite [i]) numPrimes++;
    }
    int [] primes = new int [numPrimes];
    int index = 0;
    for (int i = 2; i <= max; i++) {
        if (!isComposite [i]) primes [index++] = i;
    }
    return primes;
}

推荐答案

通过将数组的每个元素与每个可能的因子进行比较来查找素数的方法效率低下得可怕.您可以通过一次对整个阵列进行埃拉托色尼筛分来极大地改进它.除了少得多的比较之外，它还使用加法而不是除法.除法要慢得多.

Your method of finding primes, by comparing every single element of the array with every possible factor is hideously inefficient. You can improve it immensely by doing a Sieve of Eratosthenes over the entire array at once. Besides doing far fewer comparisons, it also uses addition rather than division. Division is way slower.

这篇关于用 Eratosthenes 筛法寻找素数(原文:有没有更好的方法来准备这个数组?)的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！