Java素数需要更快

Question

import java.util.*;

public class PrimeNum {
public static void main(String[] args) {
    Scanner input = new Scanner(System.in);     
    int a = input.nextInt();
    int b = input.nextInt();

    for(int i = a ; i <= b ; i++ ) {
        if ( i == 2 || i == 3 ) System.out.println(i);

        for(int j = 2; j <= (i / 2) ; j++ ) {
            if ( (i % j) == 0 ) break;
            if ( j == (i / 2) ) System.out.println(i);
        }
    }

}
}

这个程序很简单，输入2个int a和b。它将找到 a 和 b 中的任何质数。

我怎样才能让它更快？我尝试了 Math.sqrt，但在这种情况下它效果不佳:(我真的不知道，因为每当我使用它时，它都会导致很多错误。我很高兴看到有人在这种情况下使用 Squareroot。

Answer 1

我同意使用不同方法的建议，但我会尝试解释为什么你的方法不起作用。

我认为问题在于您打印结果的方式:

for(int j = 2; j <= (i / 2) ; j++ ) {
    if ( (i % j) == 0 ) break;
    if ( j == (i / 2) ) System.out.println(i);
}

这对于 i/2 效果很好，但对于 Math.sqrt(i) 会失败，因为它并不总是整数，然后 j = = Math.sqrt(i) 永远不会是真的。仅当 i 是精确平方时，您的代码才有效。

最好重构您的代码，以便您的素性测试位于单独的方法中:

boolean isPrime(int i) {
    int s = (int)Math.sqrt(i);
    for (int j = 2; j <= s; j++) {
        if (i % j == 0) { return false; }
    }
    return true;
}