Faktorisierung

[negaH]

Du testet nur alle Primzahlen bis Quadratwurzel von N, nicht bis zur Hälte von N.

Mein DECMath hast du ja schon, dann teste mal mein TSmallPrimeSieve in Unit Prime.pas. Mit diesem Sieb berechnet man sequientiell alle Primzahlen bis 2^32 in ca. 13 Sekunden (P4 1.5GHz)

Nach jedem Entfernen eines gefundenen Faktors solltest du N noch mit Prime.IsPrime(N) oder NIsProbablePrime(N) überprüfen ob es eine Primzahl ist. Wenn ja kannst du deine Fatorization schon vorzeitig beenden und N ist dann der größte übrig bleibende Primfaktor.

Etwa so:

Delphi-Quellcode:

procedure TrialDivFactorize(N: IInteger);
var
  F: Cardinal;
begin
  repeat
    F := NSmallFactor(N);
    if F > 1 then
    begin
      NDiv(N, F);
      Write(F, ', ');
    end else 
    begin
      if F = 1 then
        if NIsProbablePrime(N) then Write(NStr(N))
          else Write(NStr(N), ' composite');
      Break;
    end;
  until False;
  WriteLn;
end;

Deine Methode kannst du beschleunigen:

1.) den Fall Faktor ist 2 erschlagen wird am Anfang separat
2.) danach mit Faktor 3 weitermachen und diesen immer um +2 inkrementieren, nicht +1 !!

Das würde deine Verfahren doppelt schneller machen.

3.) ein TBit Array wird benötigt wobei jedes Bit die Zahlen 3,5,7,9,11,13,15,17 usw. bestimt. Nachdem die 3 als Faktor fertig ist wird nun in diesem Array alle Bits mit Index 3,6,9,12,15 also 3*x herausgestrichen. Alle diese Faktoren die in diesem TBIt Array markiert wurden sind KEINE Primzahlen und müssen auch nicht mehr getestet werden. Die Faktoren 9 und 15 würden also nicht mehr getestet werden. In deinem TBit Array bleibt am Ende nur die Zahlen auf FALSE die Primzahlen sind.
Du testest jetzt bis Wurzel(N).

Dies macht das Verfahren nochmals wesentlich schneller und man stösst defakto an die Grenzen dieses Verfahrens. Entweder weil die Laufzeit immer größer wird (quadratisch) oder weil der Speicherbedarf für unser TBit Array zu groß wird.


Gruß Hagen