java - 使用埃拉托色尼筛法寻找素数(最初为 : Is there a better way to prepare this array?)

Question

注意:下面的第 2 版使用埃拉托色尼筛。有几个答案对我最初提出的问题有所帮助。我选择了埃拉托色尼筛法，实现了它，并适本地改变了问题的标题和标签。感谢所有帮助过的人!

简介

我编写了这个奇特的小方法，它生成一个包含小于指定上限的素数的 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. 我可以(一次)复制整个 block 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 )使用 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;
}

Answer 1

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