Java 用埃拉托色尼筛法寻找素数（原文：有没有更好的方法来准备这个数组？）

Finding prime numbers with the Sieve of Eratosthenes (Originally: Is there a better way to prepare this array?)

提问by eleven81

Note:Version 2, below, uses the Sieve of Eratosthenes. There are several answers that helped with what I originally asked. I have chosen the Sieve of Eratosthenes method, implemented it, and changed the question title and tags appropriately. Thanks to everyone who helped!

注意：下面的第 2 版使用 Eratosthenes 筛。有几个答案对我最初提出的问题有所帮助。我选择了 Eratosthenes 筛法，实施了它，并适当地更改了问题标题和标签。感谢所有帮助过的人！

Introduction

介绍

I wrote this fancy little method that generates an array of int containing the prime numbers less than the specified upper bound. It works very well, but I have a concern.

我写了这个奇特的小方法，它生成一个 int 数组，其中包含小于指定上限的素数。它工作得很好，但我有一个担忧。

The Method

方法

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

My Concern

我的顾虑

My concern is that I am creating an array that is far too large for the final number of elements the method will return. The trouble is that I don't know of a good way to correctly guess the number of prime numbers less than a specified number.

我担心的是，我创建的数组对于该方法将返回的最终元素数量来说太大了。问题是我不知道正确猜测小于指定数字的素数个数的好方法。

Focus

重点

This is how the program uses the arrays. This is what I want to improve upon.

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

1. I create a temporary array that is large enough to hold every number less than the limit.
2. I generate the prime numbers, while keeping count of how many I have generated.
3. I make a new array that is the right dimension to hold just the prime numbers.
4. I copy each prime number from the huge array to the array of the correct dimension.
5. I return the array of the correct dimension that holds just the prime numbers I generated.

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

Questions

问题

1. Can I copy the whole chunk (at once) of temp[]that has nonzero elements to primes[]without having to iterate through both arrays and copy the elements one by one?
2. Are there any data structures that behave like an array of primitives that can grow as elements are added, rather than requiring a dimension upon instantiation? What is the performance penalty compared to using an array of primitives?

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

---

---

Version 2 (thanks to Jon Skeet):

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

---

---

Version 3 (thanks to Paul Tomblin) which uses the Sieve of Erastosthenes:

第 3 版（感谢Paul Tomblin）使用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;
}

采纳答案by Paul Tomblin

Your method of finding primes, by comparing every single element of the array with every possible factor is hideously inefficient. You can improve it immensely by doing a Sieve of Eratosthenesover the entire array at once. Besides doing far fewer comparisons, it also uses addition rather than division. Division is way slower.

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

回答by Hank Gay

The easiest solution would be to return some member of the Collections Frameworkinstead of an array.

最简单的解决方案是返回集合框架的某个成员而不是数组。

回答by Jon Skeet

Create an ArrayList<Integer>and then convert to an int[]at the end.

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

There are various 3rd party IntList(etc) classes around, but unless you're reallyworried about the hit of boxing a few integers, I wouldn't worry about it.

IntList周围有各种 3rd 方（等）课程，但除非你真的担心拳击几个整数的影响，否则我不会担心。

You could use Arrays.copyOfto create the new array though. You might also want to resize by doubling in size each time you need to, and then trim at the end. That would basically be mimicking the ArrayListbehaviour.

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

回答by unwind

Restructure your code. Throw out the temporary array, and instead write function that just prime-tests an integer. It will be reasonably fast, since you're only using native types. Then you can, for instance, loop and build a list of integers that are prime, before finally converting that to an array to return.

重构你的代码。扔掉临时数组，而是编写只对整数进行素数测试的函数。它会相当快，因为​​您只使用本机类型。然后，例如，您可以循环并构建一个质数整数列表，然后最终将其转换为要返回的数组。

回答by Bogdan

Are you using Java 1.5? Why not return List<Integer>and use ArrayList<Integer>? If you do need to return an int[], you can do it by converting List to int[]at the end of processing.

您使用的是 Java 1.5 吗？为什么不退货List<Integer>和使用ArrayList<Integer>？如果确实需要返回int[]，则可以通过int[]在处理结束时将 List 转换为 来实现。

回答by Tom Hawtin - tackline

As Paul Tomblin points out, there are better algorithms.

正如 Paul Tomblin 所指出的，有更好的算法。

But keeping with what you have, and assuming an object per result is too big:

但是与您所拥有的保持一致，并假设每个结果的对象太大：

You are only ever appending to the array. So, use a relatively small int[] array. When it's full use append it to a List and create a replacement. At the end copy it into a correctly sized array.

您只需要追加到数组中。所以，使用一个相对较小的 int[] 数组。当它被完全使用时，将它附加到一个列表并创建一个替换。最后将其复制到大小正确的数组中。

Alternatively, guess the size of the int[] array. If it is too small, replace by an int[] with a size a fraction larger than the current array size. The performance overhead of this will remain proportional to the size. (This was discussed briefly in a recent stackoverflow podcast.)

或者，猜测 int[] 数组的大小。如果它太小，则用一个比当前数组大小大几分之一的 int[] 替换。这样的性能开销将保持与大小成正比。（在最近的 stackoverflow 播客中对此进行了简要讨论。）

回答by dmckee --- ex-moderator kitten

Now that you've got a basic sieve in place, note that the inner loop need only continue until temp[i]*temp[i] > prime.

现在您已经有了一个基本的筛选器，请注意内循环只需要继续直到temp[i]*temp[i] > prime.

回答by jfs

ArrayList<>Sieve of Eratosthenes

ArrayList<>埃拉托色尼筛

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

Formula for upper bound of number of primes less than or equal to max(see wolfram.com):

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

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

回答by Yatendra Goel

Algo using Sieve of Eratosthenes

使用 Eratosthenes 筛法的算法

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

Image depicting the above algo (Grey color cells represent prime number. Since we consider all numbers as prime numbers intially, the whole is grid is grey initially.)

描绘上述算法的图像（灰色单元格代表质数。由于我们最初将所有数字视为质数，因此整个网格最初是灰色的。）

Image Source: WikiMedia

图片来源：维基媒体

回答by Rok Kralj

I have a really efficient implementation:

我有一个非常有效的实现：

1. we don't keep the even numbers, therefore halving the memory usage.
2. we use BitSet, requiring only one bit per number.
3. we estimate the upper bound for number of primes on the interval, thus we can set the initialCapacityfor the Array appropriately.
4. we don't perform any kind of division in the loops.

1. 我们不保留偶数，因此将内存使用量减半。
2. 我们使用BitSet，每个数字只需要一位。
3. 我们估计了区间上素数数量的上限，因此我们可以initialCapacity适当地设置数组。
4. 我们不在循环中执行任何除法。

Here's the code:

这是代码：

public ArrayList<Integer> sieve(int n) {
    int upperBound = (int) (1.25506 * n / Math.log(n));
    ArrayList<Integer> result = new ArrayList<Integer>(upperBound);
    if (n >= 2)
        result.add(2);

    int size = (n - 1) / 2;
    BitSet bs = new BitSet(size);

    int i = 0;
    while (i < size) {
        int p = 3 + 2 * i;
        result.add(p);

        for (int j = i + p; j < size; j += p)
            bs.set(j);

        i = bs.nextClearBit(i + 1);
    }

    return result;
}