寻找素数与埃拉托色尼的筛（原文：有没有prepare这阵更好的办法？） [英] Finding prime numbers with the Sieve of Eratosthenes (Originally: Is there a better way to prepare this array?)
问题描述
注意：版本2，下面，使用埃拉托色尼的筛。有几个答案是什么我原来问的帮助。我选择了埃拉托色尼筛的方法，实现了它，并适当改变了问题的标题和标签。感谢大家谁帮助！
简介
我写的产生为int的含质数的数组比指定的上限少这个奇特的小方法。它工作得很好，但我有一个问题。
的方法
私有静态诠释[] generatePrimes（INT最大值）{
INT [] TEMP =新INT [MAX];
温度[0] = 2;
INT索引= 1;
INT素= 1;
布尔isPrime = FALSE;
而（（黄金+ = 2）＆LT; =最大值）{
isPrime = TRUE;
的for（int i = 0; I＆LT;指数;我++）{
如果（素％temp [I] == 0）{
isPrime = FALSE;
打破;
}
}
如果（isPrime）{
临时[指数++] =黄金;
}
}
INT [] =素数的新INT [指数]
而（ - 索引＆gt; = 0）{
素数[指数] =气温[指数]
}
返回素数;
}
我的关注
我担心的是我创建的数组是元素的方法将返回的最终数量过于庞大。麻烦的是我不知道的好方法要正确预测质数少于规定数量的多少。
焦点
这是程序如何使用数组。这就是我要加以改进的。
- 我创建一个临时数组，它是
大到足以容纳每一个数字
不到极限。 - 我生成素数，而
我有多少保留计数
产生的。 - 我提出一个新的数组，它是正确的
维持有刚刚总理
数字。 - 我复制的每个素数从
巨大的数组的数组
正确的尺寸。 - 我返回正确的数组
维保存刚才总理
我生成的数字。
问题
- 我可以复制整个块（一次）的
温度[]有非零
元素素数[]
而不必通过迭代
两个数组复制的元素
一个接一个？ - 是否有任何数据结构
行为像元的阵列
可以成长为元素的添加，
而不是要求的尺寸
在实例？是什么
相比性能下降
使用原语的数组？
2版（感谢乔恩斯基特）：
私有静态诠释[] generatePrimes（INT最大值）{
INT [] TEMP =新INT [MAX];
温度[0] = 2;
INT索引= 1;
INT素= 1;
布尔isPrime = FALSE;
而（（黄金+ = 2）＆LT; =最大值）{
isPrime = TRUE;
的for（int i = 0; I＆LT;指数;我++）{
如果（素％temp [I] == 0）{
isPrime = FALSE;
打破;
}
}
如果（isPrime）{
临时[指数++] =黄金;
}
}
返回Arrays.copyOfRange（温度，0，索引）;
}
私有静态诠释[] generatePrimes（INT最大值）{
布尔[] = isComposite新的布尔[MAX + 1];
的for（int i = 2; I * I＆LT; = MAX;我++）{
如果（！isComposite [I]）{
对于（INT J =我;我* J＆LT; = MAX; J ++）{
isComposite [我* J] =真;
}
}
}
INT numPrimes = 0;
的for（int i = 2; I＆LT; = MAX;我++）{
如果numPrimes ++（isComposite [I]！）;
}
INT [] =素数的新INT [numPrimes]
INT索引= 0;
的for（int i = 2; I＆LT; = MAX;我++）{
（！isComposite [I]），如果素数[指数++] =我;
}
返回素数;
}
您找到素数的方法，通过阵列的每一个元素与每一个可能的因素是比较可怕效率低下。你可以做一个
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!
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.
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.
- I create a temporary array that is large enough to hold every number less than the limit.
- I generate the prime numbers, while keeping count of how many I have generated.
- I make a new array that is the right dimension to hold just the prime numbers.
- I copy each prime number from the huge array to the array of the correct dimension.
- I return the array of the correct dimension that holds just the prime numbers I generated.
Questions
- Can I copy the whole chunk (at once) of
temp[]that has nonzero elements toprimes[]without having to iterate through both arrays and copy the elements one by one? - 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?
Version 2 (thanks to 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:
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;
}
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 Eratosthenes over the entire array at once. Besides doing far fewer comparisons, it also uses addition rather than division. Division is way slower.
这篇关于寻找素数与埃拉托色尼的筛（原文：有没有prepare这阵更好的办法？）的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
