使用Eratosthenes筛子查找素数（原文：有更好的方法来准备此数组吗？）

Question

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

介绍

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

方法

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

我的顾虑

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

焦点

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

1. 我创建一个临时数组，该数组的大小足以容纳每个小于限制的数字。
2. 我生成素数，同时统计生成的素数。
3. 我制作了一个新的数组，该数组是仅容纳素数的正确维度。
4. 我将每个素数从巨大数组复制到正确维度的数组。
5. 我返回正确维度的数组，其中仅包含我生成的素数。

问题

1. 我是否可以（一次）复制temp[]具有非零元素的整个块，primes[] 而不必遍历两个数组并一次又一次地 复制元素？
2. 是否有任何数据结构的行为都像原始数组一样，可以随着添加元素而增长，而不是在实例化时需要一个维？与使用原始数组相比，性能损失是多少？

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

使用Erastosthenes筛网的版本3

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

Answer 1

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