java用Eratosthenes筛寻找素数（最初：有没有更好的方法来准备这个数组？）

Question

注：下面的第2版使用了埃拉托斯坦筛。有几个答案对我最初的问题有所帮助。我选择了Eratosthenes方法的筛子，实现了它，并适当地更改了问题标题和标签。感谢所有帮助过我的人

导言

我编写了这个奇特的小方法，它生成一个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. 我可以（一次）复制整个文件吗 ^具有非零的{} 元素到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（感谢使用Sieve of Erastosthenes的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;
}

Answer 1

Algo使用埃拉托斯坦筛

public static List<Integer> findPrimes(int limit) {

    List<Integer> list = new ArrayList<>();

    boolean [] isComposite = new boolean [limit + 1]; // limit + 1 because we won't use '0'th index of the array
    isComposite[1] = true;

    // Mark all composite numbers
    for (int i = 2; i <= limit; i++) {
        if (!isComposite[i]) {
            // 'i' is a prime number
            list.add(i);
            int multiple = 2;
            while (i * multiple <= limit) {
                isComposite [i * multiple] = true;
                multiple++;
            }
        }
    }

    return list;
}

图像描述上述ALGO（灰色细胞代表质数），因为我们把所有数作为素数，整体上是格子是灰色的。p>

图像源：WikiMedia

Answer 2

创建一个ArrayList<Integer>，然后在末尾转换为一个int[]

有各种各样的第三方IntList（etc）类，但是除非你真的担心装箱几个整数的影响，否则我不会担心

不过，您可以使用Arrays.copyOf来创建新数组。您可能还希望在每次需要时将大小加倍，然后在末尾进行修剪，从而调整大小。这基本上是在模仿ArrayList行为

Answer 3

最简单的解决方案是返回Collections Framework的某个成员而不是数组

Answer 4

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

Answer 5

^Eratosthenes的{}筛

// Return primes less than limit
static ArrayList<Integer> generatePrimes(int limit) {
    final int numPrimes = countPrimesUpperBound(limit);
    ArrayList<Integer> primes = new ArrayList<Integer>(numPrimes);
    boolean [] isComposite    = new boolean [limit];   // all false
    final int sqrtLimit       = (int)Math.sqrt(limit); // floor
    for (int i = 2; i <= sqrtLimit; i++) {
        if (!isComposite [i]) {
            primes.add(i);
            for (int j = i*i; j < limit; j += i) // `j+=i` can overflow
                isComposite [j] = true;
        }
    }
    for (int i = sqrtLimit + 1; i < limit; i++)
        if (!isComposite [i])
            primes.add(i);
    return primes;
}

小于或等于max的素数的上界公式（见wolfram.com）：

static int countPrimesUpperBound(int max) {
    return max > 1 ? (int)(1.25506 * max / Math.log((double)max)) : 0;
}

Answer 6

您正在使用Java1.5吗？为什么不返回List<Integer>并使用ArrayList<Integer>？如果确实需要返回int[]，可以在处理结束时将列表转换为int[]