-2

数百万未満の素数の合計を見つけようとしています。私のコードは、10万未満の素数の合計を見つけようとすると機能しますが、大きな数になると機能しません。だから私は大きな数のためにこの仕事を得るためにいくつかの助けが必要です...

import java.util.Scanner;
public class sumPrime {

  public static void main (String args []){

    long n = 2000000; int i; int j;int sum =0;
    for (i=2; i <n; i++){
        for (j=2; j<i; j++){
            if (i%j==0){
                break;
            }
        }
        if (i==j){
            sum +=i;
        }
    }
    System.out.print(sum);
  }
}
4

4 に答える 4

4

  1. 内側のループを早期に停止させることで、コードを改善できます。数値Nが素数でない場合、少なくとも 1 つの因数 (1 を除く) が より小さいか等しい必要がありsqrt(N)ます。この場合、この単純な変更により、プログラムは約 1000 倍速くなるはずです。

  2. シンプルで（より）効率的なアルゴリズムについては、エラトステネスのふるいを読んでください。

  3. バグ - あなたのsumニーズはlong. Anintはおそらくオーバーフローします。

エラトステネスのふるいの古典的な定式化には、関心のある最大の素数候補に応じてサイズが異なるブール値 (またはビットマップ) の大きな配列が必要であることに注意してください。・・・小さすぎて気になりません。また、コードはより複雑になりますが、段階的にふるいにかけることでメモリ使用量を減らすことができます。

于 2013-09-01T00:00:11.807 に答える
2

i 以下のすべての数で除算するのではなく、見つかった素数をリストに保持して、それらの素数で除算を試みることができます (素数以外の数はそれより小さい素数で割り切れるため)。

public static long sumPrime2() {
    List<Long> primes = new ArrayList<>();
    primes.add(2L);
    primes.add(3L);
    long primeSum = 5;

    for (long primeCandidate = 5; primeCandidate < 2000000; primeCandidate = primeCandidate + 2) {
        boolean isCandidatePrime = true;
        double sqrt = Math.sqrt(primeCandidate);
        for (int i = 0; i < primes.size(); i++) {
            Long prime = primes.get(i);
            if (primeCandidate % prime == 0) {
                isCandidatePrime = false;
                break;
            }
            if (prime > sqrt) {
                break;
            }
        }
        if (isCandidatePrime) {
            primes.add(primeCandidate);
            primeSum += primeCandidate;
        }
        System.out.println(primeCandidate);
    }
    System.out.println(primes.size());
    return primeSum;
}

これにより、8秒で答えが得られました

于 2013-09-01T05:13:45.953 に答える
1

i、j、sum の整数オーバーフローが疑われます - それらをすべて long にしてみてください。サンプル コードでは、Java int は 32 ビットであることを意図しているため、オーバーフローが発生することはありませんが、ある段階では確実にオーバーフローが発生します。

すでに述べたように、n の平方根まで繰り返す必要があるだけです。したがって、次の行を置き換えます。

for (i=2; i <n; i++){

と：

long limit=sqrt(n);
for (i=2; i <limit; i++){

プログラム ループの外で平方根を計算すると、処理が少し速くなることに注意してください。

また、ふるいアルゴリズムは高速になりますが、Java で n 個の要素を含む配列を作成する必要があり、ある段階でメモリ不足で失敗します。

于 2013-09-01T00:09:38.273 に答える
0

このプログラムに最適なアルゴリズムは、エラトステネスのふるいを使用します。

function sumPrimes(n)
    sum, sieve := 0, makeArray(2..n, True)
    for p from 2 to n
        if sieve[p]
            sum := sum + p
            for i from p*p to n step p
                sieve[i] := False
    return sum

次にsumPrimes(2000000)、200 万未満の素数の合計を約 1 秒で返します。合計に適切なデータ型を使用して、Java に変換することはあなたに任せます。素数を使ったプログラミングに興味がある場合は、私のブログでこのエッセイをお勧めします。

于 2013-09-01T12:24:40.817 に答える