Fatorisierung - Ablauf korrekt, aber falsche Ergebnisse

[Waldbärchen]

Hallo und guten Tag!

Ich befasse mich erst seit kurzem mit DELPHI (Version2005) und habe dazu meine alten Ideen wieder herausgeholt, die ich vor langer Zeit mit Turbo Pascal gebastelt habe. Ich will natürlich jetzt einiges verfeinern.
Hier also ein Programm zur Primzahlprüfung und Primfaktorzerlegung.
So sollte das eigentlich funktionieren:
Teil I: Eine Funktion "primpruef(a)", die den kleinsten von 1 verschiedenen Primteiler ausgibt, im Primfall also a selber.
Teil II: Eine Prozedur, die diese Funktion so oft aufruft, bis auch der letzte (größte) untersuchte Teiler prim ist. Die kleineren werden jeweils nacheinander abgespalten und in "Zerlegung" aufgezählt. Danach schließlich die entsprechenden Ausgaben.
Das Dumme an der Sache ist nur, daß ich vom Compiler keine Fehlermeldung bekomme, das Programm auch fehlerfrei abläuft, aber falsche und höchst merkwürdige Ergebnisse bringt. Bei 67 z.B. sagt es richtig, das die Zahl prim ist, die Teiler von 34 seien aber 1 x 2 x 117 und die Primzahl 117 selber habe eine Zerlegung 1 x 3 x 3 x 113!

Delphi-Quellcode:

function primpruef(a:Int64):Int64;
  {gibt den kleinsten Primteiler von a aus}
var b,i:Int64;
begin
  b:= Trunc(Sqrt(a));
  i:= 2;
While i<=b Do
  begin
    If a mod i = 0 Then
      begin
        primpruef:= a div i;
        exit;
      end
    Else
      i:= i+1;
  end;
  primpruef:= a;
end;


procedure TForm4.Button1Click(Sender: TObject);
  {gibt, falls eine Zahl nicht prim ist,
  die Primteiler aus}
var a,b,c,Primteiler:Int64;
    Zerlegung:String;
begin
  a:= StrToInt64(InputBox('Eingabe',
  'Bitte hier die zu prüfende Zahl eingeben:',''));
  b:= a;
  Zerlegung:= '1';
Repeat
  c:= b;
  b:= primpruef(b);
  If b=a Then
    begin
      ShowMessage('Die Zahl '+ IntToStr(a)
      +' ist eine Primzahl!');
      exit;
    end
  Else
    begin
      Primteiler:= c div b;
      Zerlegung:= Concat(Zerlegung,' x ',IntToStr(Primteiler));
    end;
Until b=c;
  ShowMessage('Die Zahl '+ IntToStr(a)+
  ' hat die Primfaktorzerlegung '+Zerlegung+ IntToStr(c));
end;
end.

Ich finde bei diesen Ergebnissen nicht die Stelle, über welchen Befehl das Programm stolpert.
Habt Ihr eine Idee?

Vielen Dank im Voraus,
Euer Waldbärchen

[Klaus01]

Delphi-Quellcode:

  ShowMessage('Die Zahl '+ IntToStr(a)+
  ' hat die Primfaktorzerlegung '+Zerlegung+ IntToStr(c));  // <--- hier stolperts

Hier ist der Workaround:

Delphi-Quellcode:

 begin
      Primteiler:= c div b;
      if primteiler <> 1 then
        Zerlegung:= Concat(Zerlegung,' x ',IntToStr(Primteiler));
    end;

An sich hättest Du da auch selber drauf kommen können.
Haltepunkt setzen, F8 benutzen und Variablen anschauen (Strg-F5).

Grüße
Klaus

[marabu]

Herzlich willkommen in der Delphi-PRAXiS, Waldbärchen.

Dein Algortihmus liefert immer 1 als vorletzten PrimTeiler. Die 117 entsteht durch eine Unachtsamkeit beim Anhängen des endgültig letzten Teilers - ohne Trenner. Hat Klaus aber schon erkannt.

In deiner Faktorisierungsfunktion vermisse ich die klassische Fallunterscheidung:

Delphi-Quellcode:

function MinFactor(n: Int64): Int64;
begin
  if n < 1 then
    Result := 0
  else if n mod 2 = 0 then
    Result := 2
  else begin
    Result := 3;
    repeat
      if n mod Result = 0
        then Exit
        else Inc(Result, 2);
    until (Result * Result > n);
    Result := n;
  end;
end;

Nur ungerade Faktoren müssen in der Prüfschleife betrachtet werden.

Freundliche Grüße vom marabu

[Waldbärchen]

Hallo Klaus!

Vielen Dank! Ich hatte mich die ganze Zeit gefragt, ob das Problem in (vertauschten?)Laufvariablen oder sonstwie im eigentlichen Programm stecken könnte, aber auf die Ausgabe bin ich nicht gekommen!
Übrigens danke auch für Hinweid auf F8. Jetzt weiß ich endlich, wie man so ein Programm mit Einzelschritten durchgehen kann. In meinem Anleitungsbuch (von MuT) sind überhaupt keine Tips für die Fehlersuche und das Debugging!

Viele Grüße vom Waldbärchen

[Waldbärchen]

Hallo Marabu!

Gerade erst, als ich mein Post geschickt hatte, habe ich bemerkt, daß in der Zwischenzeit noch eine weitere Antwort eingetroffen ist.

Zitat von marabu:

Dein Algortihmus liefert immer 1 als vorletzten PrimTeiler.

Das ist ja auch so gewollt, denn das wird ja letzlich als Abbruchbedingung geprüft. Ich muß aber die andere Variable (c) ausgeben, das habe ich inzwischen gemerkt.

Zitat:

In deiner Faktorisierungsfunktion vermisse ich die klassische Fallunterscheidung:
Nur ungerade Faktoren müssen in der Prüfschleife betrachtet werden.

Das war mir im Prinzip klar, aber ich wollte das Ding erstmal überhaupt zum Laufen bringen - vielleicht bringe ich ihm später das Fliegen bei...

Ich konnte - und wollte - Deinen Funktionstext natürlich nicht einfach bei mir reinkopieren. Oder genauer: Ich habe es erstmal versucht und die Funktion und Parameter umbenannt, aber das hat nicht geklappt. Ich habe den Vorschlag mit dem Result hinengenommen, da braucht man ja jetzt überhaupt keine var-Deklaration mehr! Jetzt tuts erstmal, die Fallunterscheidung für die 2er-Schritte kommt morgen dran.

Nochmal vielen Dank Ihr Beide
Euer Waldbärchen