Problem 37: Abschneidbare Primzahlen

Gesucht werden die 11 Primzahlen, die sowohl von rechts als auch von links verkürzt, immer eine Primzahl ergeben! [ das englische Original ]

Um dieses Problem zu lösen, muss man sich im ersten Schritt überlegen, wie man eine gegebene Primzahl schrittweise um eine Ziffer verkürzen kann. Dies ist für die Verkürzung von der rechten Seite kein Problem, da man einfach durch 10 teilen muss. Die nachfolgende Grafik zeigt, wie man im selben Schritt auch die Zahlen erzeugen kann, die durch eine Verkürzung von links entstehen würden:

Veranschaulichung des Algorithmus zur gleichzeitigen Verkürzung einer Zahl von rechts und links
Veranschaulichung des Algorithmus zur gleichzeitigen Verkürzung einer Zahl von rechts und links

Dieser Algorithmus lässt sich recht einfach in einer Methode abbilden, die gleichzeitig die Existenz der sich ergebenen Zahlen in einer Liste von Primzahlen prüft:

private boolean test( int num ) {
   int l2r = 0, r2l = num, factor = 1;
   while( r2l > 10 ) {
      l2r += ( r2l % 10 ) * factor;
      r2l /= 10;
      factor *= 10;
 
      if( !candidates.contains( l2r ) || !candidates.contains( r2l ) )
         return false;
      }
 
      return true;
}

Zur Vorbereitung suche ich alle Primzahlen kleiner als 1.000.000 und verwerfe alle Zahlen, die eine der Ziffern 0, 2, 4, 6 oder 8 enthalten, da diese bei einer Verkürzung irgendwann immer durch 2 teilbar wären:

@Override
public void prepare() {
   super.prepare();
   candidates = new ArrayList< Integer >();

   Sieve sieve = new Sieve( 1000000 );
   int next = sieve.next();
   candidates.add( next );
 
   while( next != -1 ) {
      if( ( String.valueOf( next ).matches( "^[468]\\d+" ) == false )
       && ( String.valueOf( next ).matches( "\\d+[02468]$" ) == false ) ) {
         candidates.add( next );
      }
      next = sieve.next();
   }
 
   IO.debugln( "found " + candidates.size() + " candidates" );
}

Damit gestaltet sich die Prüfung der verbleibenden Primzahlen recht einfach :

public String solve() {
   int sum = 0;
 
   for( int num : candidates ) {
      if( test( num ) && ( num > 10 ) ) {
         IO.debugln( "found " + num );
         sum += num;
      }
   }
 
   return IO.i2s( sum );
}

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

<< Problem 36 Übersicht Problem 38 >>

Willkommen in Nico Dannebergs Netzwerk

%d Bloggern gefällt das: