用埃拉托斯特尼筛子寻找素数（最初：有没有更好的方法来准备这个数组？

注意：下面的版本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;
}

我的顾虑

我担心的是，我正在创建一个数组，该数组对于该方法将返回的最终元素数来说太大了。麻烦的是，我不知道有一个好方法可以正确猜测小于指定数的素数。

重点

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

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

版本3（感谢Paul Tomblin）使用Erastosthenes的Sieve：

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