Problem 50: Summe aufeinander folgender Primzahlen

Gesucht wird die Primzahl (kleiner als eine Million), die als Summe der meisten aufeinander folgenden Primzahlen berechnet werden kann! [das englische Original]

Die Lösung dieses Problems scheint nicht sehr schwer zu sein. Beim genaueren Betrachten wird aber klar, dass „nur“ die meisten aufeinander folgenden Primzahlen gesucht werden, was nicht heißt, dass diese Serien immer bei 2 starten müssen. Dementsprechend kommt jede Primzahl als Start einer Reihe in Frage. Diese kann man in den folgenden zwei Schritten finden:

1) Alle Primzahlen zwischen 2 und 1.000.000 finden:

@Override
public void prepare() {
   super.prepare();

   limit = 1000000;
   candidates = new ArrayList< Integer >();
   Sieve sieve = new Sieve( limit );

   while( sieve.hasNext() )
      candidates.add( sieve.next() );
}

2) Alle möglichen Summen bilden und das Maximum merken:

@Override
public String solve() {
   IO.infoln( candidates.size() + " candidates have to be tested!" );

   int[] results = new int[ candidates.size() ];
   int min = 0, maxP = 0, maxT = 0;
 
   for( int i=0; i<candidates.size(); i++ ) {
      for( int j=min; j<=i; j++ ) {
         results[ j ] += candidates.get( i );
         if( results[ j ] + candidates.get( i ) > limit ) {
            min = j+1;
         }
         if( candidates.contains( results[ j ] ) && j!=i ) {
            if( maxT < i - j + 1 ) {
               maxT = i - j + 1;
               maxP = results[ j ];
               IO.infoln( "found prime sum " + maxP + " added of " + maxT + " terms! [ " + i + " : " + j + " ]" );
            }
         }
      }
   }
 
   return IO.i2s( maxP );
}

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

<< Problem 49 Übersicht Problem 51 >>

Willkommen in Nico Dannebergs Netzwerk

%d Bloggern gefällt das: