2

このコードを実行して、200 万未満のすべての素数の合計を出力しようとしています。このループは終わることはありません。コードの何が問題なのか誰か教えてもらえますか? しかし、それはより小さな数で機能するようです。

public static void main(String[] args) {

        long result = 1;

        for(int i=0; i<2000000; i++) {
            if(isPrime(i)) {
                result+= i;
            }
        }
        System.out.println(result);

    }
private static boolean isPrime(long n) {
    boolean result = false;

    for(long i=2; i<(long)Math.sqrt(n); i++) {
        if(n%i == 0) {
            result = false;
            break;
        }
        else result = true;
    }
    return result;
}
4

5 に答える 5

5

あなたは2isPrimeによる除算のみをテストしています：

private static boolean isPrime(long n) {
    boolean result = false;

    for(long i=1; i<n/2; i++) {
        if(n%2 == 0) {
            result = false;
            break;
        }
        else result = true;
    }
    return result;

}

iそれは、2から始まるすべての除算でなければなりません：

for(long i=2; i<n/2; i++) {
    if(n%i == 0) {
      ...

実際には、現在のバージョンでは、奇数はすぐに停止するのではなく、n最大 2 で割り続けます。n/2n = 21 とします。3 番目のステップで 3 で割って終了するのではなく、1 から 10 までを 2 で割っています。

return誤った結果が得られるだけでなく、ステートメントに到達するまでに必要以上に時間がかかります。

編集：より迅速な結果については、このエラトステネス法のふるいをチェックしてください：

public static long sumOfPrimes(int n) {

    long sum = 0;

    boolean[] sieve = new boolean[n];
    for(int i = 2; i < Math.sqrt(n); i++) {
        if(!sieve[i]) {
            for(int j = i * i; j < n; j += i) {
                sieve[j] = true;
            }
        }
    }

    for(int i = 2; i < n; i++) {
        if(!sieve[i]) {             
            sum += i;
        }
    }

    return sum;
}

編集 #2 : 新しいバージョンでいくつかのバグが見つかりました。これが修正されたものです：

private static boolean isPrime(long n) {
    boolean result = false;

    if(n == 2 || n == 3) return true;

    for (long i = 2; i <= (long) Math.sqrt(n); i++) {
        if (n % i == 0) {
            result = false;
            break;
        } else
            result = true;
    }

    System.out.println(n + " " + result);
    return result;
}
于 2012-06-04T11:48:33.203 に答える
2

バグがありますisPrime()

テストは次のようにする必要があります。

if(n%i == 0) { ...

で割ったときにすべての数値がゼロになるため2、 ではなくでカウントを開始する必要があります。11

また、過去に行く必要はありませんMath.sqrt(n)。

これを次のように変更する必要があります。

private static boolean isPrime(long n) {
    long max = (long)Math.sqrt(n);
    for (long i = 2; i < max; i++) {
        if (n % i == 0) {
            return false;
        }
    }
    return true;
}

参考までに、この変更により、PC でプログラムをテストしたところ、1 秒未満で完了し、次の結果が得られました。143064094810

于 2012-06-04T11:48:36.660 に答える
0

単純な関数は、実行するたびにまで (または少なくとも まで)isPrimeのすべての素数を計算する必要があります。isPrime 関数がその結果をキャッシュしていることを確認してください!isqrt(i)

于 2012-06-04T11:46:54.547 に答える
0

テスト済みでバグのないプライムチェック機能

static boolean isPrime(int n) {
    if (n == 1) return false;

    for(int i = 2; i <= n/2; i++)
        if(n % i == 0)
            return false;

    return true;
}
于 2013-08-28T06:59:52.120 に答える
0

これは、JOptionPane、つまり Java GUI を使用した Prime の完全なプログラムです。

import javax.swing.*;

public class ChkPrime {
    public static void main(String[] args) throws NumberFormatException {
        String str = JOptionPane.showInputDialog(null, "Enter any number: ","Input...", 3);

        try {
            int num = Integer.parseInt(str);


            if (num == 1)
                JOptionPane.showMessageDialog(null, "Your inputed no. " + num + " is not prime.","Error!", 0);

            for(int i = 2; i <= Math.sqrt(num); i++) {
                if(num % i == 0) {
                    JOptionPane.showMessageDialog(null, "Your inputed no. " + num + " is not prime.","Error!", 0);
                    System.exit(0);
                }
            }

            JOptionPane.showMessageDialog(null, "Your inputed no. " + num + " is prime.","Yeh! Got it!", 1);
        }

        catch (NumberFormatException e) {
            JOptionPane.showMessageDialog(null, "Please input numbers...","Error!", 0);
            main(null);
        }
    }
}
于 2014-01-19T13:17:14.747 に答える