Primfaktorzerlegung läuft viel zu langsam...

[fapsons]

Hallo Leute,

habe zur Primfaktorzerlegung hier einen Quelltext gefunden, den ich entsprechend abgeändert habe.
Er läuft allerdings, jedoch viel zu langsam, sodass bei größeren Werten das Programm abstürzt.
Könnt ihr mir da weiterhelfen, was ich evtl. verbessern kann?

Danke
-fapsons-

Delphi-Quellcode:

function Is_Prime(x: int64): Boolean;
var i :Integer;
begin
  result := true;
  for i := 2 to x-1 do
    if x mod i = 0 then result := false
end;



function Get_Prime_Factors(x: Int64): TIntArray;
var i, j, k :Integer;
    r       :TIntArray;
begin
  r := TintArray.Create;
  k := 1;
  for i := 2 to x do
  begin
       j := 0;
       while x mod i = 0 do
       begin
          x := x div i;
          inc(j)
       end;

       if j = 1 then
       begin
         r.ints[k] := i;
         k := k + 1;
       end;
  end;
  result := r;
end;

[mkinzler]

Delphi-Quellcode:

if x mod i = 0 then 
begin
    result := false;
    exit;
end;

[Chris P]

Hi,

also erstens brauchst du nur ungerade Teiler zu testen und zweitens schickt es wenn die for-Schleife
nur bis Wurzel aus x läuft, denn x = Wurzel(x) * Wurzel(x).

[MatWur]

PFZ ist eine komplizierte Sache, wenn sie für grosse Zahlen durchgeführt wird. Die traditionelle Methode des durchtesten wird dabei viel zu langsam. Als erste Optimierung würde ich vorschlagen in deiner Funktion Is_Prime die Testdivisionen auf die ungeraden Zahlen zu beschränken und nur bis SqRt (x) zu testen. Die Testdivisionen sollten später sogar nur die bisher ermittelten Primzahlen umfassen, um nochmal weniger Testdivisionen zu erhalten.
Falls es dir nur um die PFZ einiger bestimmter Zahlen geht empfehle ich dir folgende Seite, sie hat ein Java Applet das sehr gut und schnell mit modernen Methoden faktorisiert:
http://www.alpertron.com.ar/ECM.HTM

Ausserdem empfehle ich dir, dich mit dem "kleinen Fermat'schen Satz" zu befassen (Mathematik), der ist für die Bestimmung von Primzahlen bei grossen Zahlen elementar.

mfg

Matthias

[fapsons]

Vielen Dank schon mal für eure Hilfe...

Hab es noch nicht versucht mit deinen Verbesserungsvorschlägen MatWur, aber wie setze ich das denn um, dass meine For-Schleife nur ungerade Werte annimmt?

Wahrscheinlich gibt es für mein Problem auch eine viel einfachere Lösung und zwar besteht mein Wert, der zerlegt werden soll aus Faktoren, die jeweils Primzahlen sind.

Also X := 3 * 5 * 7 * 11 oder ähnlich
der höchste Faktor meines Wertes kann max. 31 sein.

Es müsste nur ausgegeben werden, welche einzelnen Faktoren mein Produkt enthält...

Hier nochmal der aktuelle Code mit der ersten Änderung:

Delphi-Quellcode:

function Is_Prime(x: int64): Boolean;
var i :Integer;
begin
  result := true;
  for i := 2 to x-1 do
    if x mod i = 0 then result := false
end;



function Get_Prime_Factors(x: Int64): TIntArray;
var i, j, k :Integer;
    r       :TIntArray;
begin
  r := TintArray.Create;
  k := 1;
  for i := 2 to x do
  begin
       j := 0;
       if x mod i = 0 then
       begin
          x := x div i;
          inc(j);
       end;

       if j = 1 then
       begin
         r.ints[k] := i;
         k := k + 1;
       end;
  end;
  result := r;
end;

[Chris P]

So habe ich das gelöst:

Delphi-Quellcode:

function IsPrime(const Value: Cardinal): Boolean;
var
   t: Cardinal;
begin
   if (Value = 2) then
   begin
      Result := TRUE;
      Exit;
   end;

   if (Value < 2) or (Value mod 2 = 0) then
   begin
      Result := FALSE;
      Exit;
   end;

   t := 3;
   while (t * t <= Value) do
   begin
      if (Value mod t = 0) then
      begin
         Result := FALSE;
         Exit;
      end
      else
         t := t + 2;
   end;
   Result := TRUE;
end;
// -----------------------------------------------------------------------------
function Factorize(const V: Cardinal): TFactors;
var
   t, x, Count: Cardinal;
begin
   t := 2;
   x := V;

   Count := 0;
   SetLength(Result, 0);

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

[MatWur]

ich wollte gerade anfangen, aber Chris P hat schon eine brauchbare Lösung abgeliefert.
Zuerst wird getestet ob die Zahl gleich 2 ist, wenn ja prim und raus.
Dann wird getestet ob es 0,1 oder eine gerade Zahl>2 ist, wenn ja nicht prim und raus.
Dann werden beginnend mit t=3 die ungeraden Zahlen abgetestet und falls ein Faktor gefunden wird -> nicht prim und raus.

Wenn bei deinen Zahlen tatsächlich nur Primzahlen bis 31 vorkommen kannst du den Schritt
while (t * t <= Value) do
ersetzen durch
while (t <= 31) do, damit kannst du bei grossen Zahlen noch einmal Zeit sparen.

Das er den Typ Cardinal statt wie du den Typ Int64 genommen hat sollte hoffentlich kein Problem sein. Weenn doch, bitte rückfragen.

mfg

Matthias

Edit: PS

eine for Schleife für ungerade Zahlen erhälst du folgendermaßen:

Delphi-Quellcode:

for i := 0 to 19 do begin
  n := 2*i+1;
  {rechnen mit n} end;

in dieser Schleife hat n nacheinander die Werte 1, 3, 5, ..., 37, 39

[Chris P]

@MatWur: Danke für die ergänzende Erklärung :thumb:

[Nikolas]

Ich würde diese Schreibweise bevorzugen:

Delphi-Quellcode:

for i:=1 to floor(sqrt(x)) do
 if (x mod (2*i+1)) = 0 then 
 begin 
   result:= false; 
   exit; 
 end;

Macht eigentlich nichts anderes, müsste aber schneller sein, da nicht bei jedem Durchlauf t*t mit x verglichen werden muss, sondern die maximale Anzahl der Durchläufe schon von Anfang an feststeht.
Und jemand mit einem etwas geschulten mathematischen Blick erkennst den Ausdruck 2*i+1 sofort als Reihe der ungeraden Zahlen.
Ich glaube schon gelesen zu haben, dass der Compiler aufsteigende Schleifen auch gerne durch downtoschleifen ersetzt, da anscheinend das prüfen auf Variable=0 einfacher ist als Variable=SonstiergWert. Ist hier zwar nicht direkt der Fall, da im niedrigsten Fall noch auf i=1 getestet wird, aber wär mal einen Gedanken wert, da die aufsteigende Schleife wahrscheinlich früher abbricht, als die absteigende.

[Chris P]

Das mag ja sein nur du rufst in jedem Schleifendurchlauf floor(...) und sqrt(...) auf.
Außerdem ist sqrt ungenau da es mit Fließkommazahlen arbeitet.

Das hat man bei bei meiner Lösung nicht.