0

Project Euler の 10番目の問題を解こうとしているのですが、なぜかうまくいきません。私はプログラミングと Java がまったく初めてなので、なぜそれが機能しないのか理解できません。問題のポイントは、2,000,000 未満のすべての素数の合計を見つけることです。

/*  The sum of the primes below 10 is 2 + 3 + 5 + 7 = 17.

    Find the sum of all the primes below two million.
*/  

public static void main(String[] args){

    long n = 1;
    long sum = 0;
    long limit;

    System.out.println("Enter the limit of n: ");
    limit = TextIO.getlnLong(); //TextIO is another input method
    while (limit <= 0){
        System.out.println("Enter the limit of n (must be positive): ");
        limit = TextIO.getlnLong();

    }       

    while (n < limit){ 
        n++;
        if (n % 2 != 0 && n % 3 != 0 && n % 5 != 0 && n % 7 != 0 && n != 1 || n == 2 || n == 3 || n == 5 || n == 7){ //this is my prime checking method, might be flawed

            sum = sum + n;  
            System.out.println(+sum);
        } //end if

    }//end while

    System.out.println("The sum of the primes below 2,000,000 is: " +sum);

} //end of main
4

5 に答える 5

4

効率的な素数チェック方法については、エラトステネスのふるいを読んでください。

于 2012-06-07T21:39:54.120 に答える
2

あなたの主な方法は壊れています。2と数の平方根の間に除数がない場合、その数は素数です。13 * 13は、素数チェック関数に合格します。

for i to sqrt(n):
   if(n % i == 0):
       OH NO NOT PRIME DO SOMETHING HERE?
if something is prime
   add some stuff
于 2012-06-07T21:40:09.123 に答える
1

些細な解決策よりも優れた2つの解決策を次に示します。

1) 奇数を繰り返し(偶数の素数のみが既に合計に含まれています)、それらが素数であるかどうかを確認します。

private static boolean isOddPrime(int x) {
    for ( int i = 3 ; i*i <= x ; i+=2 ){ 
        if ( x % i == 0 ) {
            return false;
        }
    }
    return true;
}

private static void sumOfPrimes1(int n) {       
    long sum = 2;
    for ( int i = 3 ; i < n ; i+=2 ) {
        if ( isOddPrime(i) ) {
            sum+=i;
        }
    }
    System.out.println(sum); 
}

2)エラトステネスのふるいを使う

private static void sumOfPrimes2(int n) {
    boolean notPrimes[] = new boolean[n];   // default = false
    for ( int i = 2 ; i*i < n ; i++ ) {
        if ( !notPrimes[i] ) {
            for ( int j = i*i ; j < n ; j+=i ){
                notPrimes[j] = true;
            }
        }
    }
    long sum = 2 ;
    for ( int i = 3 ; i < n ; i+=2 ) {
        if ( !notPrimes[i] ) {
            sum+=i;
        }
    }
    System.out.println(sum);
}

Java のデフォルトのブール値がfalse.

パフォーマンス:

n           |    2000000        8000000       16000000
------------+-------------------------------------------
Solution 1  |    1309 ms        8574 ms       22757 ms
Solution 2  |    119 ms         696 ms        1624 ms
于 2014-11-12T21:23:18.443 に答える
-4 
public static void main(String args[])
{
  long n = 1;
  long sum = 0;
  long limit=Integer.parseInt(args[0]);

  while (n < limit)
  {
    n++;
    if(n % 2 != 0 && n % 3 != 0 && n % 5 != 0 && n % 7 != 0 && n != 1 || n == 2 || n == 3 || n == 5 || n == 7)
    {
      sum = sum + n;
    }
  }


    System.out.println("The sum of the prime numbers = " +sum);
 }
于 2012-11-02T17:54:34.257 に答える