Problem 60: Primzahlen-Paar-Mengen

Gesucht wird die kleinste Summe von fünf Primzahlen, die jeweils paarweise zusammengesetzt auch Primzahlen ergeben! [das englische Original]

Da es wieder einmal um Primzahlen geht, braucht es natürlich auch wieder meine Klasse für ein „Sieb des Eratosthenes. Damit erzeuge ich mir eine Liste mit allen Primzahlen unter 10.000 und arbeite diese Basis ab.

Leider brauche ich 5 (!!!) in einander verschachtelte Schleifen. Allerdings kann man die Länge jeder einzelnen Schleife sehr kürzen, in dem jede innere Schleife

  1. immer beim nachfolgenden Element der äußeren Schleife startet und
  2. eine innere Schleife nur gestartet wird, wenn alle Elemente aller äußeren Schleifen bereits paarweise Primzahlen bilden.

Durch diese beiden Einschränkungen löst mein Programm das Problem immerhin recht fix binnen 5,5 Sekunden:

@Override
public String solve() {

   int len = candidates.size();
   String[] primes = new String[ 5 ];

   for( int a = 0; a < len; a++ ) {
      primes[ 0 ] = Integer.toString( candidates.get( a ) );

      for( int b = a + 1; b < len; b++ ) {
         primes[ 1 ] = Integer.toString( candidates.get( b ) );

         if( testPrimePairs( primes[ 0 ], primes[ 1 ] ) ) {
            IO.debugln( "=> " + primes[ 0 ] + "\n\t=> " + primes[ 1 ] );

            for( int c = b + 1; c < len; c++ ) {
               primes[ 2 ] = Integer.toString( candidates.get( c ) );

               if( testPrimePairs( primes[ 0 ], primes[ 1 ], primes[ 2 ] ) ) {
                  IO.debugln( "\t\t=> " + primes[ 2 ] );

                  for( int d = c + 1; d < len; d++ ) {
                     primes[ 3 ] = Integer.toString( candidates.get( d ) );

                     if( testPrimePairs( primes[ 0 ], primes[ 1 ], primes[ 2 ], primes[ 3 ] ) ) {
                        IO.debugln( "\t\t\t=> " + primes[ 3 ] );

                        for( int e = d + 1; e < len; e++ ) {
                           primes[ 4 ] = Integer.toString( candidates.get( e ) );

                           if( testPrimePairs( primes ) ) {
                              IO.debugln( "\t\t\t\t=> " + primes[ 4 ] );
                              IO.debugln( "found!!!" );
                              int sum = candidates.get( a ) + candidates.get( b ) + candidates.get( c ) + candidates.get( d ) + candidates.get( e );
                             return IO.i2s( sum );
                          }
                       }
                    }
                 }
              }
           }
        }
     }
  }

   return "-1";
}

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

<< Problem 59 Übersicht Problem 61 >>

Willkommen in Nico Dannebergs Netzwerk

%d Bloggern gefällt das: