使用Eratosthenes的筛子找到素数(原来:有更好的方法来准备这个阵列吗？)

Question

注意:下面的版本2使用了Eratosthenes的Sieve.有几个答案有助于我最初的问题.我选择了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. 我可以复制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)使用了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

通过将数组的每个元素与每个可能的因子进行比较,找到素数的方法非常低效.你可以通过立刻在整个阵列上进行Eratosthenes筛选来极大地改善它.除了做更少的比较,它还使用加法而不是除法.分工比较慢.

Answer 2

ArrayList<> 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 3

创建一个ArrayList<Integer>,然后转换为int[]最后一个.

IntList周围有各种第三方(等)类,但除非你真的担心拳击几个整数的命中,我不会担心它.

您可以使用Arrays.copyOf创建新数组.您可能还希望每次需要时将尺寸加倍,然后在最后修剪.这基本上就是模仿ArrayList行为.

Answer 4

Algo使用Eratosthenes的Sieve

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

描绘上述算法的图像(灰色单元代表素数.由于我们将所有数字视为素数,因此最初的网格是灰色的.)

图片来源:WikiMedia