Problem 51: Ziffern ersetzen in Primzahlen

Gesucht wird die kleinste Primzahl, die durch Ersetzen gleicher Ziffern der Start einer Serie von 8 Primzahlen ist! [das englische Original]

Da ich kein Gefühl dafür hatte, in welchem Bereich eine 8er Serie von Primzahlen zu suchen war, habe ich mit Hilfe meines  “Sieb des Eratosthenes” alle Primzahlen zwischen 100 und 1.000.000 ausgelesen. Dies habe ich nach ihrer Länge sortiert in einem Zwischenspeicher abgelegt:

@Override
public void prepare() {
   super.prepare();
 
   mem = new Hashtable< Integer, ArrayList< LargeNumber > >();
   Sieve sieve = new Sieve( 1000000 );
 
   for( int prim : sieve ) {
      if( prim > 100 ) {
         LargeNumber num = new LargeNumber( prim );
         int key = num.getLength();
         if( !mem.containsKey( key ) ) {
            mem.put( key, new ArrayList< LargeNumber >() );
         }
         mem.get( key ).add( num );
      }
   }
}

Auf Basis dieser Vorbereitung musste ich dann nur noch meine Klasse für Große Zahlen um eine Methode erweitern, die eine bestimmte Ziffer durch eine andere ersetzt:

@Override
public String solve() {
   Enumeration< Integer > keys = mem.keys();
   while( keys.hasMoreElements() ) {
      int key = keys.nextElement();
      IO.debugln( "key = " + key );
      for( LargeNumber prim : mem.get( key ) ) {
         for( int i = 1; i < prim.getLength(); i++ ) {
            int count = 1;
            String result = prim.toString();
            for( int x = 0; x < 11; x++ ) {
               if( x != prim.getDigit( i ) ) {
                  LargeNumber num = prim.replaceDigit( prim.getDigit( i ), x );
                  if( mem.get( key ).contains( num ) ) {
                     count++;
                     result += " > " + num;
                  }
               }
            }
 
            if( count >= 6 ) {
               IO.infoln( "found series: " + result );
            }
            if( count == 8 ) {
               return prim.toString();
            }
         }
      }
   }
 
   return null;
}

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

<< Problem 50 Übersicht Problem 52 >>

Willkommen in Nico Dannebergs Netzwerk

%d Bloggern gefällt das: