Java 素数查找效率

Question

我想对所有值小于 10 的素数求和。

这是我的代码：

    boolean kontroll = true;
    long limit = 10;
    long checker = 2;
    long sum = 0;

    while (checker < 10) {
        for (long i = 3; i < Math.sqrt(checker); i += 2) {
            if (checker % 2 == 0) {
                kontroll = false;
                break;
            } else {
                if (checker % i == 0) {
                    kontroll = false;
                } 
            }
        } if (kontroll) {
            sum += checker; 
            System.out.println("Prim: " + checker);
        }
        checker++;
        kontroll = true;
    }
    System.out.println(sum);

我得到这个输出：

Prim: 2
Prim: 3
Prim: 4
Prim: 5
Prim: 6
Prim: 7
Prim: 8
Prim: 9
44

这个版本有什么问题？如果我删除 Math.sqrt(checker); 程序可以运行，但速度很慢。我不能取检查器的平方根吗？

Answer 1

当checker为非负数且小于等于8时，

3大于Math.sqrt(checker)。

试试这个：

boolean kontroll = true;
long limit = 10;
long checker = 2;
long sum = 0;

while (checker < 10) {
    if (checker != 2 && checker % 2 == 0) { // move this check out of the loop and correct condition
        kontroll = false;
    } else {
        long max = (long)Math.sqrt(checker);
        for (long i = 3; i <= max; i += 2) { // change < to <=
            if (checker % i == 0) {
                kontroll = false;
                break; // add break for better performance
            } 
        }
    }
    if (kontroll) {
        sum += checker; 
        System.out.println("Prim: " + checker);
    }
    checker++;
    kontroll = true;
}
System.out.println(sum);

Answer 2

您的 kontroll 变量分配有 true，并且您正在从 3 循环到 sqrt(checker)，在您的情况下 checker 将低于 10.

所以，你的代码只会进入你的循环一次，当 checker = 10 (3 < sqrt(10)) 和其他时候，它们只是经过到

if (kontroll) { //remember, your kontroll assigned to true =)
    sum += checker; 
    System.out.println("Prim: " + checker);
}

总和总是相加。干杯！

Answer 3

一个优化版本，最多打印某个数字的质数。

final List<Integer> primes = new ArrayList<>(Collections.singletonList(2));

/**
 * Print prime numbers up to {@code n} inclusive
 */
public void findPrimes(int n) {
    // check only odd numbers
    for (int i = 3; i <= n; i += 2) {
        isPrime(i);
    }
    System.out.println(primes);
}

// a function which does have side effects (adds to the primes collection)
private boolean isPrime(final int i) {
    // we really need to check for divisors only up to sqrt
    int sqrt = (int)Math.sqrt(i);
    // and we really need to find only prime divisors since any
    // number can be written as a product of prime numbers
    for (int prime : primes) {
        if (i % prime == 0) {
            return false;
        }
        if (prime > sqrt) {
            break;
        }
    }
    primes.add(i);
    return true;
}

Java 素数查找效率

Java Prime finder efficiency

java

performance

square-root