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 >> |