Entwickler-Ecke :: Thema anzeigen - Berechnung der kleinsten Zahl mit den Teilern 1-20

Mashalla - Sa 12.07.08 14:30
Titel: Berechnung der kleinsten Zahl mit den Teilern 1-20

Delphi-Quelltext

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
26:
27:
28:
29:
30:
31:

function TMainForm.Get_Number: Integer;
var Number_Counter: Integer;
    Divisor_Counter: Integer;
    Continue: Boolean;

begin
  Result := 0;
  Continue := true;

  // Schleife für die Zahlen
  for Number_Counter := 2520 to 2000000000 do
    begin
      // Schleife für die Teiler
      for Divisor_Counter := 2 to 20 do
        begin
          if Continue = true then
            begin
              // prüft auf Teilbarkeit und bricht ab sobald ein Teiler spackt
              if Number_Counter mod Divisor_Counter = 0 then
                Continue := true
              else
                break;
            end;
        end;
      if (Divisor_Counter = 20) then
        begin
          Result := Number_Counter;
          exit;
        end;
    end;
end;

Die obige Funktion soll die kleinste Zahl ausgeben, die alle Teiler von 1 bis 20 beinhaltet. Jetzt bin ich allerdings mit der Range schon knapp unter der Integer Grenze angekommen und die Funktion gibt mir immer "0" zurück. Liegt ein Fehler in der Funktion vor oder ist die Zahl wirklich so riesig?

PS: Falls ihr testet, rechnet mit Laufzeiten um 30 Sekunden bei obigen Grenzen :)

Hidden - Sa 12.07.08 15:06

Hi,

Über ihre Primfaktorzerlegung kommst du ja an die Zahl: Sie muss alle Primfaktoren ihrer Teiler enthalten.

Bilde mal die Primfaktorzerlegungen aller Zahlen bis 20. Nun suchst du für jede Primzahl das häufigste Vorkommen und schreibst es heraus; das sind:

Somit ist die gesuchte Zahl das Produkt davon und damit (2^4) * (3^3) * 5 * 7 * 11 * 13 * 17 * 19.

Wenn du nun dazu ein Programm schreiben willst, müsstest du das isolieren der Primzahlen nurnoch in einen Algorithmus packen und am Ende das Produkt der Funde bilden.

Edit: Mit dem Windows-Taschenrechner komme ich dann auf Gausis Ergebnis :) .

Edit2: Du solltest dir abgewöhnen, bei jedem begin-Block doppelt(4 Leerzeichen) einzurücken; so kommst du schnell an den Rand und machst den Quelltext unleserlich. Auch würde ich garnicht bei jedem begin zwei Zeilenumbrüche machen:

Delphi-Quelltext

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
26:

function TMainForm.Get_Number: Integer;
var 
  Number_Counter: Integer;
  Divisor_Counter: Integer;
  Continue: Boolean;
begin
  Result := 0;
  Continue := true;

  // Schleife für die Zahlen
  for Number_Counter := 2520 to 2000000000 do begin
    // Schleife für die Teiler
    for Divisor_Counter := 2 to 20 do begin
      if Continue = true then begin
        // prüft auf Teilbarkeit und bricht ab sobald ein Teiler spackt
        if Number_Counter mod Divisor_Counter = 0 then
          Continue := true
        else break;
      end;
    end;
    if (Divisor_Counter = 20) then begin
      Result := Number_Counter;
      exit;
    end;
  end;
end;

Zum Highlight: http://www.delphi-forum.de/viewtopic.php?t=83487

mfG,

Gausi - Sa 12.07.08 15:13

Hm, bei mir spuckt der irgendwie auch keine aus...er sollte aber. :gruebel:

Denn: du greifst nach der for-Schleife auf die Schleifenvariable (Divisor_Counter) zu. Das gibt normalerweise eine Warnung, da der Wert nach der Schleife undefiniert ist oder sein kann. Mach mal eine While-Schleife draus.

Außerdem: Welchen Sinn hat Continue? Das ist immer True - da musst du an der Programmlogik noch was tüfteln. ;-)

Reinhard Kern - Sa 12.07.08 21:12

Hidden hat folgendes geschrieben:

Hi,

Über ihre Primfaktorzerlegung kommst du ja an die Zahl: Sie muss alle Primfaktoren ihrer Teiler enthalten.

Klar, war auch mein erster Gedanke, und bei 1 - 20 geht das in ein paar Minuten mit Taschenrechner oder sogar ganz ohne Hilfe (ein Blatt Papier braucht man schon). Aber eine Schleife, die millardenmal durchlaufen wird, ist einfach viel geiler...

Gruss Reinhard

Timosch - Sa 12.07.08 21:25

Reinhard Kern hat folgendes geschrieben:

Hidden hat folgendes geschrieben:

Hi,

Über ihre Primfaktorzerlegung kommst du ja an die Zahl: Sie muss alle Primfaktoren ihrer Teiler enthalten.

Mann, du bist wirklich noch ein echter Programmierer von altem Schrot und Korn.

Entwickler-Ecke.de based on phpBB
Copyright 2002 - 2011 by Tino Teuber, Copyright 2011 - 2026 by Christian Stelzmann Alle Rechte vorbehalten.
Alle Beiträge stammen von dritten Personen und dürfen geltendes Recht nicht verletzen.
Entwickler-Ecke und die zugehörigen Webseiten distanzieren sich ausdrücklich von Fremdinhalten jeglicher Art!