gpt4 book ai didi

java - 优化素数筛选的速度 (Java)

转载 作者:行者123 更新时间:2023-11-30 03:07:14 25 4
gpt4 key购买 nike

我正在开发一种 Java 方法,它创建 boolean 数组 isPrime:

boolean[] isPrime;

其中质数标记为“true”,其余标记为“false”。
当我这样做时,我还想计算找到的素数数量:

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++:

不起作用,因为筛子多次将某些非素数的值设置为“假”(例如 45 bcs 3*15 = 45 和 9*5 = 45)。
那么有人知道我如何重写这个程序,以便将所有非素数设置为“假”仅一次吗?

或者一般来说,有人可以提出让该方法更快的方法吗?

最佳答案

如果您使用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());
}

我还修复了您的逻辑中的一些错误。例如。您的内部循环将 j 步进 2,而您的外部循环并未删除所有偶数(从 3 开始)。

您当然可以改进这一点 - 谷歌是您的 friend 。 :)

关于java - 优化素数筛选的速度 (Java),我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/34455635/

25 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com