Gesucht wird die Summe aller Primzahlen kleiner 2 Millionen! [das englische Original]

Analog zu den Problemen 3 und 7 nutze ich hier das das “Sieb des Eratosthenes”, um die gewünschten Primzahlen zu finden und zu summieren:

/**
 * Initializes the {@link #sieve} with number from 0 to {@link #max}
 */
@Override
public void prepare() {
   super.prepare();

   max = 2000000;
   sum = 0;

   sieve = new int[ max ];

   for( int i=0; i<max; i++ ) {
      sieve[ i ] = i;
   }
}

/**
 * Runs the algorithm of the "Sieve of Eratosthenes" and sums up every
 * found prime factor.
 *
 * @return the sum of all primes below {@link #max}
 * @see <a href="http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes">Wikipedia</a>
 */
@Override
public String solve() {
   for( int i=2; i<max; i++ ) {
      if( sieve[ i ] > -1 ) {
         IO.debugln( "new prime: " + sieve[ i ] );

         sum += sieve[ i ];

         for( int j=i; j<max; j+=i ) {
            sieve[ j ] = -1;
         }
      }
    }

    return IO.l2s( sum );
}

Den vollständigen Quellcode der Klasse für die Lösung des Problems 10 kann man sich hier anschauen!

<< Problem 9

Übersicht

Problem 11 >>