0

このプログラムを実行するためのより効率的な方法があるかどうか疑問に思っていますか?

数値が小さい場合は問題なく動作しますが、数値が大きくなると時間も指数関数的に増加します。つまり、1000000 のような数字には永遠に時間がかかります

import java.util.*;

public class SumOfPrimes {

public static void main(String args[]) {
    Scanner in = new Scanner(System.in);
    long number = 0;

    System.out.println("This program outputs the sum of the primes of a given number.");
    System.out.print("Please enter a number: ");
    number = in.nextLong();

    System.out.println("The sum of the primes below "+number+" is: "+sumOfPrimes(number));
}

public static long sumOfPrimes(long n){
    long currentNum = 2;
    long sum = 0;
    if (n > 2){
        sum = sum + 2;
    }

    while (currentNum <= n) {
        if (currentNum % 2 != 0 && isPrime(currentNum)) {
            sum = sum + currentNum;
        }
        currentNum++;
    }
return sum;
}

public static boolean isPrime(long currentNum){
    boolean primeNumber = true;

    for (long test = 2; test < currentNum; test++) {
        if ((currentNum % test) == 0){
            primeNumber = false;
        }
    }

return primeNumber;
}
}
4

4 に答える 4

5

より優れた素数検出アルゴリズムがありますが、簡単な修正として、現在の数値の平方根までの因数をテストするだけで済みます。平方根。

long stop = (long) Math.sqrt(currentNum);
for (long test = 2; test <= stop ; test++) {

falseさらに、因子が見つかった場合はループを抜けて戻り、数の合成を証明します。

より効率が必要な場合は、エラトステネスのふるいを実装して、それ自体が素数である可能性のある因子のみをチェックすることができます。

于 2013-03-18T23:46:11.493 に答える
1

素数を見つけるたびに一連の素数を保存する必要があるため、毎回すべての数で割ることは避けてください。

この事:currentNum % 2 != 0として書くことができますcurrentNum & 1。

また、アルゴリズムが間違っています。入力として 3 を指定してみてください。

于 2013-03-18T23:50:35.287 に答える
1

Eratosthenes Sievie を使用します: http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes O(n log n log n) で与えられた数以下のすべての素数を見つけることができ、表全体を 1 回調べる必要があります。

于 2013-03-18T23:57:28.247 に答える
0

私は1つ書いていました.すべてが正しいことを確認することはできません.私は自分のマシンで1000000をテストしましたが、31ミリ秒かかりました. 必要なメモリ:1000000*1bytes=1mb

public class FindPrime {

/**
 * @param args
 */
public static void main(String[] args) {
    long begin=System.currentTimeMillis();
    System.out.println(findPrime(1000000));

    System.out.println("cost time="+(System.currentTimeMillis()-begin)+"ms");

}

public static long findPrime(int max){
    boolean data[]=new boolean[max+1];
    long sum=0;
    int stop=(int) Math.sqrt(max);
    for(int i=2;i<=stop;i++){
        if(data[i]==false){
            sum+=i;

            int index=i+i;
            while(index<=max){
                data[index]=true;
                index=index+i;
            }
            //System.out.println(i);
        }
    }

    stop=stop+1;

    for(;stop<=max;stop++){
        if(data[stop]==false){
            sum+=stop;
            //System.out.println(stop);
        }
    }

    return sum;
}

}

于 2013-03-19T02:19:42.343 に答える