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

}
}

このプログラムは単純で、2intaとbを入力します。aとb内の素数を検索します。

どうすればこれを速くできますか？Math.sqrtを試しましたが、この場合はうまく機能しません:(使用するたびに多くのバグが発生するため、よくわかりません。この場合、誰かがSquarerootを使用するのを見てみたいです。

4

3 に答える 3

2

別のアプローチを使用するという提案には同意しますが、あなたのアプローチが機能しない理由を説明しようと思います。

問題は、結果を印刷する方法にあると思います。

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;
}
于 2012-08-18T08:21:16.383 に答える
0

このhttp://en.wikipedia.org/wiki/Sieve_of_Eratosthenesアルゴリズムを使用できます。その高速で実装が簡単です。そのアルゴリズムの下限（a）を定義できないため、まったく同じではありませんが、2からbまでのすべての要素を見つけたら、aとbの間の数値だけを返すことができます。

于 2012-08-18T08:20:10.843 に答える
0

偶数が素数になることはめったにないので、奇数だけをチェックするのはどうですか...

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);
  }
}
于 2012-08-18T08:30:02.280 に答える