Problem 58: Spiralförmige Primzahlen

Gesucht wird die kleinste Seitenlänge einer spiralförmig aufgebauten Matrix, bei der der Anteil von Primzahlen auf den beiden Diagonalen geringer als 10% ist! [das englische Original]

Da bereits in Problem 28 eine solche Matrix gegeben war, konnte ich den Algorithmus zum Springen über die Diagonalelemente wiederverwenden. Damit muss man nur jedes Element auf eine Primzahl prüfen, um das gewünschte Verhältnis zu finden:

@Override
public String solve() {

   int num = 1, cnt = 1, prm = 0, diff = 0;
 
   do {
      diff += 2;
      num += diff; if( Mathe.isPrime( num ) ) prm++;
      num += diff; if( Mathe.isPrime( num ) ) prm++;
      num += diff; if( Mathe.isPrime( num ) ) prm++;
      num += diff; if( Mathe.isPrime( num ) ) prm++;
      cnt += 4;
      IO.debugln( "got " + prm + " of " + cnt + " (" + ( ( float ) prm / ( float ) cnt ) + ") by " + ( diff + 1 ) + " side length" );
   } while( prm * 10 > cnt );
 
   return IO.i2s( diff + 1 );
}

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

<< Problem 57 Übersicht Problem 59 >>

Willkommen in Nico Dannebergs Netzwerk

%d Bloggern gefällt das: