-2

1 から 100 までのすべての素数を出力するには、以下をどのように変更しますか? 以下には、素数ではない数字 2 が返されるという問題があります。2%2 が 0 として返されるため、数値 2 の if(i%number == 0) 条件が満たされます。

public class Test {

    /**
     * @param args
     */
    public static void main(String[] args) {
        for(int i=1; i<=100; i++){
            if(isPrime(i)){
                System.out.println(i + " is a prime number");
            }else{
                System.out.println(i + " is not a prime number");
            }
        }

    }
    public static boolean isPrime(int number){
        for(int i=2; i<=number; i++){

            if(i%number == 0){
                return false;
            }else{
                return true;
            }
        }
        return false;
    }

}
4

7 に答える 7

2

これは、素数かどうかを判断するアルゴリズムです。

  • 数は 2 未満ですか？その場合は false を返します。
  • 数は2か3ですか？その場合は、true を返します。
  • 数字は4ですか？その場合は false を返します。
  • 数値の平方根を取り、次の整数に切り上げます。これは小さな素数の場合はオプションですが、大きな数の決定を高速化します。
  • 5 から数値 (または数値) の平方根までループし、2 ずつインクリメントします。
    • これまでに求めた素数でループ数を割ります。
    • 除算のモジュラスがゼロの場合、false を返します。
  • ループが完了したら、true を返します。
于 2013-07-23T17:50:45.413 に答える
1

ここにはいくつかの問題があります。まず、数値が素数かどうかをチェックするときは、素数をチェックする実際の数値までのすべての数値を決してチェックしないでください。数の平方根までのすべての素数をチェックすれば、常に十分です。

そのエラーを修正するには、for ループ条件を見て、それに応じて編集します。

for(int i=2; i<=number; i++)

次に、関数が戻ると停止します。現在、if/else ステートメントで:

if (i%number == 0) {
   return false;
} else {
   return true;
}

この条件が一度でも true を返す else ステートメントに進む場合は、意図したすべての数値をチェックしたときにのみ実際に true を返すようにする必要があります。

さらに、基本ケースが何であるかを慎重に検討したとは思いません。あなたが最後の行で言っていることは、以前にすべてが亀裂をすり抜けた場合、その数は素数ではないと想定する必要があるということです。よく考えてみてください。きっと解決できると思います。

于 2013-07-23T17:34:38.747 に答える
1

これは機能します。2 は、素数をテストする場合の特殊なケースです。ますます大きなものを探し始めると、エラトスフェネスのふるいを見たくなるかもしれません。

すべての素数は別の数の倍数です。例として 3 を取り上げます。ふるいを使用して、3 が素数であることがわかった場合、3 の倍数をすべて「無視」するため、結果として生じる素数を見つけるのにかかる時間が短縮されます。それは物事をスピードアップします...ALOT :)

 public class JavaApplication47 {

 public static void main(String[] args) {

    for(int i=1; i<=100; i++){
        if(isPrime(i)){
            System.out.println(i + " is a prime number");
        }else{
//                System.out.println(i + " is not a prime number");
        }
    }
}

public static boolean isPrime(int n) {
for(int i=2; 2*i<n; i++) {
    if(n%i==0)
        return false;
}
return true;
}
}

SIEVE の例 - 実装されていません - 参照と理解のために使用できます。

static boolean [] allPrimes = new boolean[10000];

public static void fillTheSieve(){
    Arrays.fill(allPrimes, true);
    allPrimes[0] = allPrimes[1] = false; //1 and 0 are false. winning

    for (int i = 2; i < allPrimes.length; i++) {
        //check if prime, if so getmultiples and declae false
        if(allPrimes[i]){
            for (int j = 2; i*j<allPrimes.length; j++) {
                allPrimes[i*j] = false;

            }
        }

    }
}
于 2013-07-23T17:48:49.330 に答える
0

プライムを扱う際に考慮すべき点がいくつかあります。最初に 2 の特別なケースを指定できます (つまり、if(number == 2)... のようなもの)。

i<=number素数ではないことを確認するためにどこまで行く必要があるかだけを検討するためにすべての方法をチェックする際のエラーに加えて 、ヒントはすでにi*iまたはで与えられていますMath.sqrt

インクリメントのもう 1 つのことは、i++それが何を伴うかを考えることです。これは最初の 100 個の素数についてのみであることは理解していますが、常にパフォーマンスについて考えておく必要があります。本当にすべての数字 (2,3,4,5,6...) をチェックする必要がありますか? (ヒント: 2 で割り切れるかどうかチェックした場合は、4,6,8 などをチェックする必要はありません.

最後に、return ステートメントで、数値が素数であるか素数でない場合にのみ、false/true に設定するフラグを使用することを検討してbooleanください。また、return ステートメントを 1 つだけ使用する必要があります。

それが役立つことを願っています。

于 2013-07-23T17:43:13.403 に答える
0

素数の定義では、素数になることはできないと明確に述べられています。

つまり、isPrime(1)false を返す必要があります。あなたの実装は何をしますか。

しかし、isPrime(2)true を返す必要があります。あなたの実装はそうではありません。(2 % 2 == 0)2からN-1ではなく、2からNまでのすべての数字をチェックしているため、そうではありません。最後の数 N は、常にゼロの剰余を生成します。(N % N == 0)

于 2013-07-23T17:38:17.130 に答える
-4

これを試してください

public static boolean isPrime(int number) {
    for(int i = 2; i * i <= number; i++) {
        if (i % number == 0) {
            return false;
        } else {
            return true;
        }
    }
    return true;
}
于 2013-07-23T17:34:23.287 に答える