Problem 5: Kleinstes Vielfaches

Gesucht wird die kleinste positive Zahl, die ganzzahlig durch alle Zahlen von 1 bis 20 teilbar ist! [das englische Original]

Bei dieser Aufgabe war gar keine richtige Programmierung notwendig. Ich habe einfach an das Produkt aller Zahlen von 1 bis 20 gedacht, um anschließend alle Faktoren zu streichen, die durch einen anderen Faktor bereits in das Produkt eingebracht werden.

Beispielsweise entfallen die 2 und die 8, da der Faktor 16 beide Teiler in das Produkt einbringt und enthalten sein muss, da sie das Quadrat der 4 ist. Auf der anderen Seite entfällt die 15, da die 5 als Primzahl und die 9 als Quadrat der 3 enthalten sein müssen.

Mit diesem Wissen gestaltet sich die Lösungsmethode recht übersichtlich:

   @Override
   public String solve() {
 
      int res = 1;
      // res *= 2; // replaced by 16
      // res *= 3; // replaced by 9
      // res *= 4; // replaced by 16
      res *= 5;
      // res *= 6; // replaced by 9 and 16
      res *= 7;
      // res *= 8; // replaced by 16
      res *= 9;
      // res *= 10; // replaced by 5 and 16
      res *= 11;
      // res *= 12; // replaced by 9 and 16
      res *= 13;
      // res *= 14; // replaced by 7 and 16
      // res *= 15; // replaced by 5 and 9
      res *= 16;
      res *= 17;
      // res *= 18; // replaced by 9 and 16
      res *= 19;
      // res *= 20; // replaced by 5 and 16
 
      return IO.i2s( res );
   }

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

<< Problem 4 Übersicht Problem 6 >>

Kommentar verfassen

Willkommen in Nico Dannebergs Netzwerk

%d Bloggern gefällt das: