Problem 27: Quadratische Primzahlen

Gesucht werden die Koeffizienten a und b der quadratischen Funktion x2+ax+b, für die die Funktion die meisten Primzahlen für aufeinanderfolgende Werte für x >= 0 erzeugt! [ das englische Original ]

Da die Problemstellung den Wertebereich für die beiden Koeffizienten zwischen -1000 und 1000 festlegt, würden beim Probieren aller Möglichkeiten 4.000.000 Kombinationen entstehen. Diese Anzahl kann man über 2 Regeln deutlich verringern:

  1. Da für den ersten Wert von x = 0 das Ergebnis der Funktion immer b ist, kommen für b also nur Primzahlen in Frage!
  2. Da für den zweiten Wer von x = 1 das Ergebnis der Funktion immer ( 1 + a + b ) ist, darf a nicht kleiner als 1-b sein (da Primzahlen immer größer als Null sind)!

Zur weiteren Vereinfachung des Quellcodes überprüfte ich noch einmal die vorangegangenen Probleme, bei denen Primzahlen im Fokus standen. Dabei entdeckte ich eine Ähnlichkeit der Probleme 3, 7 und 10, so dass ich mich entschied, das “Sieb des Eratosthenes” in eine eigene Klasse auszulagern!

Damit ergibt sich folgender übersichtlicher Code für die Lösung des Problems:

@Override
public String solve() {
  int max = 0, maxA = 0, maxB = 0;
 
  for( int i = 0; i < primes.size(); i++ ) {
    int b = primes.get( i );
    for( int a = 1-b; a < 1000; a++ ) {
      int n = 0, res = b;
      while( cache.contains( res ) || Mathe.isPrime( res ) ) {
        if( !cache.contains( res ) )
          cache.add( res );
 
        n++;
        res = n*n + a*n + b;
      }
 
      if( n > max ) {
        max = n; maxA = a; maxB = b;
        IO.debug( "new maximum found: " );
        IO.debugln( "a=" + a + ", b=" + b + ", n=" + n );
      }
    }
  }
 
  return IO.i2s( maxA * maxB );
}

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

<< Problem 26 Übersicht Problem 28 >>

Kommentar verfassen

Willkommen in Nico Dannebergs Netzwerk

%d Bloggern gefällt das: