Primfaktorzerlegung läuft viel zu langsam...

[Nikolas]

Es würde mich wundern, wenn das der Fall wäre. Ich bin davon ausgegangen, dass der Compiler sieht, dass x innerhalb der Schleife nicht geändert wird und daher das floor(Sqrt(x)) nur einmal berechnet und sich merkt.
Inwiefern soll sqrt ungenau sein? Um ganz sicher zu gehen könnte man floor noch mit ceil austauschen, dann ist man auf der sicheren Seite, so lange sqrt keinen Fehler macht der größer als 1 ist :)
Und für Zahlen, bei denen ein so großer Fehler auftreten kann, sollte diese Art der Überprüfung auch nicht angewendet werden.

[Chris P]

Ich bin mir nicht sicher ob der Compiler das weiß, ob x innerhalb der Schleife verändert wird.
Ich denke, es wird bei jedem Durchlauf erneut berechnet.

Auf jeden Fall sind meine und deine Variante möglich.
Nur ich persönlich versuche Fließkommazahlen zu vermeiden wo es geht.

[fapsons]

Super ChrisP, bin begeistert. Deine Variante läuft einwandfrei.
Vielen Dank!!!

Jetzt hätte man nur noch das selber schaffen müssen...;) Aber ich bin leider noch ein blutiger Anfänger...*G*

[fapsons]

Ein Problem habe ich noch, könnte allerdings zu nem größeren werden...;)

Was ist, wenn mein x ein int64 sein muss.
Dann kann ich doch keine For-Schleife benutzen, oder?

Gibt es dafür auch eine Lösung?

[Chris P]

Freut mich!

Wenn du meine Variante einigermaßen nachvollziehen kannst, kannst du dich ja
mal an den Fermat versuchen. Das wäre dann die nächste Verbesserung.

P.S: Mit Int64 sollte es ebenfalls ohne Probleme gehen. Ersetze einfach Cardinal durch Int64.

[fapsons]

Die Funktion läuft soweit bis zum Wert 3234846615.
Mit dem letzten Wert, den ich benötige, läuft es leider nicht mehr...:(
100280245065

Ne Idee, woran es liegt?

Delphi-Quellcode:

 primzahlen := Tintarray.Create;
 primzahlen := Factorize(3234846615);


function Factorize(const V: int64): TIntArray;
var
   t, x, Count: Cardinal;
begin
   result := TIntArray.Create;
   t := 2;
   x := V;

   Count := 0;

   while (t <= x) do
   begin
      if (x mod t = 0) then
      begin
         Count := Count + 1;
         Result.ints[Count] := t;
         x := x div t;
         t := 2;
      end
      else
         t := t + 1;
   end;
end;

[Chris P]

Probier mal:

Delphi-Quellcode:

var
   t, x, Count: Int64;

[fapsons]

Super ChrisP,

bist mein persönlicher Held des Tage...;)! Tausenddank!

[Chris P]

Kein Problem :wink:

Freut mich wenn ich dir helfen konnte ...

Gruß
Chris P

[MatWur]

also sortieren^^

@ Chris P: kein Problem :mrgreen:

@ all: der Compiler erkennt den Ausdruck floor(sqrt(x)) als Konstante und berechnet ihn nur einmal. Innerhalb von for-Schleifen sind *immer* Anfangs- und Endwert der Schleife vor Schleifenbeginn bekannt bzw. wurden (1 mal) berechnet.

@ fapsons: es gibt mehrere Lösungsmöglichkeiten für dein problem mit der Schleife.
1.) du kannst theoretisch die Schleife durch eine 'while' oder eine 'repeat' Schleife ersetzen (ist aber kompliziert)
2.) besser du schreibst deine Schleife mit einem normalen Integer und übergibst dessen Wert innerhalb der Schleife einfach an eine Variable vom Typ Int64. Bsp:

Delphi-Quellcode:

var
  i: integer;
  i_gross: int64;
begin
  for i := 0 to 10 do begin
    i_gross := i;
    {rechnen mit i_gross} end;
end;

mfg

Matthias