java - 用Eratosthenes筛子查找素数(最初为: Is there a better way to prepare this array?)

注意:下面的版本2使用Eratosthenes筛网。有几个答案可以帮助我解决最初提出的问题。我选择了Eratosthenes的Sieve方法，实现了该方法，并适当地更改了问题标题和标签。感谢所有提供帮助的人!

介绍

我写了这个小巧的方法，该方法生成一个包含小于指定上限的质数的int数组。它工作得很好，但我有一个担心。

方法

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

我的顾虑

我担心的是，我创建的数组对于该方法将返回的最终元素数而言太大。问题是我不知道正确猜出小于指定数字的质数的好方法。

焦点

程序就是这样使用数组的。这是我要改进的地方。

我创建一个临时数组
足够容纳每个数字
小于限制。

我生成素数，而
记数我有多少
产生。

我制作了一个正确的新数组
仅容纳素数的尺寸
数字。

我从
巨大的阵列
正确的尺寸。

我返回正确的数组
仅包含素数的维度
我生成的数字。

问题

我可以一次复制整个块吗？
具有非零值的temp[]primes[]的元素
无需遍历
两个数组并复制元素
逐个？

是否有任何数据结构
表现得像原始数组
随着元素的添加而增长
而不是需要尺寸
在实例化时？是什么
与性能损失相比
使用原始数组？

版本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);
}

使用Paul Tomblin的版本3(感谢Sieve of Erastosthenes):

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

最佳答案

通过将数组的每个元素与每个可能的因素进行比较来查找质数的方法效率低下。您可以一次对整个数组执行Sieve of Eratosthenes来极大地改善它。除了进行少得多的比较外，它还使用加法而不是除法。除法要慢得多。