-3 
package PrimeNum;

public class primeNum {
public static void main(String args[]){
    int flag = 0;
    /*
    for(int i = 2; i <= 100; i++){
        if(i % 2 != 0 && i % 3 != 0 && i % 4 != 0 && i % 5 != 0 && 
                i % 6 != 0 &&  i % 7 != 0 && i % 8 != 0 && i % 9 != 0 && i % 10 != 0 ){
            System.out.print(i + " ");
        }
    }
    */
    System.out.println();

    for(int i = 2; i <= 100; i++){

        for(int j = 2; j <= 10; j++){
            if(i % j != 0) { 
                flag++;
            }
        }

        if(flag == 9 || flag == 8){
            System.out.print(i + " ");
            flag = 0;
        }
    }
}

}

コードは Java を使用して作成されており、ループ全体で 2 と 3 だけを 100 に出力する理由がわかりません。何か助けてください。

4

5 に答える 5

0

すべての数字をテストし、除数である数字を数え、その量が基準に一致するときにそれを出力するというあなたの考えは良いですが、テストを少し逆にします。

素数には正の約数がちょうど 2 つあり、1 とその数自体です。

2 と数値 - 1 の間のすべての数値をテストすると、正確に 0 の約数が見つかるはずです。これはすべての数値に当てはまり、約数ではない約数を知る必要はなく、すべての数値ですべての約数をテストする必要はありません。25 は大きいため、10 の約数にはなりません。

public static void simplePrintPrimesUpTo(int max) {
    // test every number between 2 and max inclusive
    for (int number = 2; number <= max; number++) {
        int foundDivisors = 0;

        // test every divisor between 2 and 1 less than the current number
        for (int divisor = 2; divisor < number; divisor++) {
            if (number % divisor == 0) {
                foundDivisors++;
            }
        }

        if (foundDivisors == 0)
            System.out.print(number + " ");
    }
    System.out.println();
}

これはさらに最適化できます。除数の興味深い性質の 1 つは、

n の除数は、n の平方根以下でなければなりません

つまりdivisor <= sqrt(number)、内側のループで上限として使用すると、必要なテストの量が大幅に削減されます。int の平方根を計算するのは残念ながら見苦しいですが、その式は両側で 2 乗することができ、テストはより簡単になります。

(divisor)^2 <= (sqrt(number))^2

に簡略化できます

(divisor)^2 <= number

次に実行できる最適化は、除数が見つかった場合に除数のテストをスキップすることです。2 であろうと 10 であろうと問題ではありません。見つかった場合は素数ではありません。結果は次のようになります

public static void optimizedPrintPrimesUpTo(int max) {
    nextNumber:
    for (int number = 2; number <= max; number++) {

        for (int divisor = 2; (divisor * divisor) <= number; divisor++) {
            if (number % divisor == 0) {
                // skip testing this number, continue in the outer loop
                continue nextNumber;
            }
        }

        System.out.print(number + " ");
    }
    System.out.println();
}
于 2013-08-06T10:30:15.537 に答える