注意：下面的版本 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;
}
我的顾虑
我担心的是我创建的数组对于该方法将返回的最终元素数量来说太大了。问题是我不知道正确猜测小于指定数字的素数数量的好方法。
重点
这就是程序使用数组的方式。这是我想要改进的地方。
- 我创建了一个足够大的临时数组，可以容纳每个小于限制的数字。
- 我生成质数，同时计算我生成了多少。
- 我制作了一个新的数组，它的维数正确，可以只保存素数。
- 我将每个素数从巨大的数组复制到正确维度的数组中。
- 我返回仅包含我生成的素数的正确维度的数组。
问题
temp[]我可以将具有非零元素的整个块（一次）复制 到primes[]而不必遍历两个数组并一个一个地复制元素吗？- 是否有任何数据结构的行为类似于可以随着元素的添加而增长的基元数组，而不是在实例化时需要维度？与使用基元数组相比，性能损失是多少？
版本 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 筛法：
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;
}
