java - Java Prime Number 需要更快

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

Answer 2

您可以使用此http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes算法。它的实施快速且简单。它不完全相同，因为您不能为该算法定义下限 (a)，但您可以在找到从 2 到 b 的所有元素后，只返回 a 和 b 之间的数字。

Answer 3

只检查奇数怎么样，因为偶数很少是素数......

if(a==2) System.out.println(2);
if((a%2)==0) a++;
for(int i = a ; i <= b ; i+=2 ) {
  if(i == 3 ) System.out.println(i);
  int root = (int) Math.sqrt(i);

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