优化素数筛 （Java） 的速度

Question

我正在Java中研究一种创建布尔数组isPrime的方法：

boolean[] isPrime;

其中质数用“真”标记，其余的用“假”标记。< br >同时，我还想数一数找到的素数:

int numPrimesFound;

基本思想是使用埃拉托斯特尼筛。到目前为止，我的方法看起来像这样：

public Sieve(final int limit) {

    long startTime = System.currentTimeMillis();

    boolean[] isPrime = new boolean[limit];
    this.isPrime = isPrime;

    for (int i=3; i<=limit ;i+=2) {
        isPrime[i] = true;                        //sets all even numbers to true
    }

    isPrime[2] = true;
    numPrimesFound = 1;                           //special case of '2'

    for (int i = 3; i * i <= limit; i += 2) {
        if (isPrime[i] == true) {
            for (int j = i; i * j <= limit; j += 2) {

                isPrime[i * j] = false;           //has a multiple ==> not a prime

                numPrimesFound++;                 //doesn't work yet
            }
        }
    }

    long stopTime = System.currentTimeMillis();   //measuring execution time
    System.out.println("Sieve: " + (stopTime - startTime) + " milliseconds.")

}

所以我的问题是

numPrimesFound++:

因为筛子多次将一些非质数的值设置为“false”（例如45 bcs 3*15=45和9*5=45），所以不起作用
那么，有人知道我如何重写这个程序，以便只将所有非质数设置为“false”一次吗？

或者一般来说，任何人都可以建议使方法更快吗？

Answer 1

您感到困惑：

找到numPrimes；可以，但它必须在（int j=i；i*j）的循环之外

你的主循环必须走得更远（否则你忘记了大于sqrt（极限）的素数）

 for (int i = 3; i < limit; i += 2) 

在埃拉托斯特尼筛中，标记几次“非素数”是正常的。

和i*j

结果是可以的，但只能用

final int limit=40000; // 50 000 is too big !

用它代替你的内循环，你至少可以达到1000000。

 for (int z = i*2; z<limit; z+=i)
    isPrime[z] = false;           //has a multiple ==> not a prime

你可以用比特集

Answer 2

下面是我的版本(它只计算包含输入数的可能质因数的集合):

import java.util.BitSet;
import java.util.Scanner;

public class Main {

public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    System.out.println("Enter the interval limit: ");
    int limit = sc.nextInt();
    int max = (int) Math.sqrt(limit);
    long start = System.currentTimeMillis();
    BitSet intArray = new BitSet(max);

    // 1 is not prime
    intArray.set(0);

    // 2 is the first prime number, so the first step is to filter out all even numbers
    for (int i = 2; i < limit; i+=2) {
        intArray.set(i);
    }

    //all remaining number will be odd
    int currentNumber = 3;
    // i is the multiplicator and will be adjusted with the current number , in order to avoid repetition
    int i = 3;
    int temp;

    while (currentNumber <= max) {
        // flag multiple of the current prime number
        while (true) {
            temp = (currentNumber * i);
            if (temp > max) break;
            intArray.set(temp - 1);
            i += 2;
        }
        //all non-prime numbers until now are already flagged, therefore we can find the next prime number by checking the set-status.
        while (true) {
            currentNumber += 2;
            if (currentNumber > max) break;
            if (!intArray.get(currentNumber - 1)) {
                i = currentNumber;
                break;
            }
        }
    }

    int b = 0;
    for (int n = max -1 ; n > 0; n--){
        if (!intArray.get(n)){
            b = n + 1;
            break;
        }
    }
    System.out.println("There are " + (max - intArray.cardinality()) + " PRIMES and the biggest is: " + b);
    System.out.println("Time in total: " + ((System.currentTimeMillis() - start) / 1000.0) + "s");
}
}

要检查1亿个数字，我的i7 3770k台式电脑需要大约0,7秒。

Answer 3

如果您使用 BitSet，则可以要求它的基数。

public BitSet primes(final int limit) {

    long startTime = System.currentTimeMillis();
    BitSet isPrime = new BitSet(limit);
    // A bitSet starts all zeros but with a sieve - evrything must start prime.
    isPrime.flip(0, limit);

    // 0 and 1 are not prime
    isPrime.clear(0);
    isPrime.clear(1);

    for (int i = 2; i * i <= limit; i += 2) {
        if (isPrime.get(i)) {
            // Remove all multiples of i.
            for (int j = 2; i * j <= limit; j += 1) {
                isPrime.clear(i * j);
            }
        }
    }

    long stopTime = System.currentTimeMillis();   //measuring execution time
    System.out.println("Sieve: " + (stopTime - startTime) + " milliseconds.");
    return isPrime;
}

public void test() {
    BitSet primes = primes(50);
    System.out.println("Primes: " + primes);
    System.out.println("Count: " + primes.cardinality());
}

我还修复了你逻辑中的几个错误。E、 g.你的内循环是按2步进j，而你的外循环不是删除所有偶数（从 >开始）。

你当然可以改进这一点——谷歌是你的朋友。：）