Problem 35: Zirkuläre Primzahlen

Gesucht werden alle Primzahlen kleiner 1.000.000, die auch nach Rotation ihrer Ziffern in allen Fällen eine Primzahl sind! [ das englische Original ]

Im ersten Schritt habe ich mir alle möglichen Primzahlen als potentiell Kandidaten gesucht. Dafür konnte ich einfach meine Klasse für das „Sieb von Eratosthenes“ benutzen. Dank des Hinweises eines Kollegen spart man hier eine Menge Rechenzeit, wenn man alle Kandidaten ignoriert, die eine der Ziffern 0, 2, 4, 6 oder 8 enthält, denn diese würde ja bei einem Schritt der Rotation als Primzahl entfallen, so bald diese Ziffer am Ende steht:

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

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

Um nun jeden verbliebenen Kandidaten zu testen, braucht es nur noch eine Methode zum Rotieren einer gegeben Zahl. Damit lassen sich die gesuchten Primzahlen leicht finden:

@Override
public String solve() {
   int not = 0;
   ArrayList< Integer > current = new ArrayList< Integer >();

   for( int prime : candidates ) {
      not = 0;
      current.clear();
 
      if( tested.contains( prime ) == false ) {

         int len = Mathe.getLength( prime );
         current.add( prime );
         tested.add( prime );
 
         for( int i=0; i<len-1; i++ ) {
            prime = Mathe.rotate( prime, len );
            if( candidates.contains( prime ) ) {
               if( current.contains( prime ) == false ) {
                  current.add( prime );
                  tested.add( prime );
               }
            } else {
               not = 1;
               i = len;
            }
         }
 
         if( not == 0 ) {
            IO.debugln( "found new set: " + current );
            found.addAll( current );
         }
      } 
   }
 
   return IO.i2s( found.size() );
}

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

<< Problem 34 Übersicht Problem 36 >>

Willkommen in Nico Dannebergs Netzwerk

%d Bloggern gefällt das: