AGB  ·  Datenschutz  ·  Impressum  







Anmelden
Nützliche Links
Registrieren
Zurück Delphi-PRAXiS Code-Bibliothek Library: Algorithmen Delphi Faktorisierung von Zahlen

Faktorisierung von Zahlen

Ein Thema von CalganX · begonnen am 30. Mai 2005
Antwort Antwort
CalganX

Registriert seit: 21. Jul 2002
Ort: Bonn
5.403 Beiträge
 
Turbo Delphi für Win32
 
#1

Faktorisierung von Zahlen

  Alt 30. Mai 2005, 18:02
Jede ganze Zahl, die keine Primzahl ist, lässt sich als ein Produkt von endlich vielen Primzahlen darstellen. In der Schule lernt man das unter dem Namen Primfaktorzerlegung kennen. In diesem Beitrag möchte ich ein paar Algorithmen sammeln, um eine Zahl in ihre Faktoren zu zerlegen.

Brute-Force-Methode
Die Haudrauf-Methode besteht nur daraus alle ganzen Zahlen von 2 bis n/2 zu durchlaufen und ihre Teilbarkeit zu überprüfen. Hier bei ist es nicht nötig diese Zahlen auf Primalität zu überprüfen, da die Vielfachen der Primzahlen automatisch herausfallen. Ich habe einfach mal diese Brute Force-Methode zusammengehackt:
Delphi-Quellcode:
type
  TPFactor = record
    Base: longint;
    Power: integer;
  end;
  TPFactors = array of TPFactor;

function Factorize(const n: longint): TPFactors;
var
  idx: longint;
  iCount: longint;
  iTemp: longint;
begin
  SetLength(Result, 0);
  iCount := 0;
  iTemp := n;
  idx := 2;
  while (idx <= (n div 2)) do begin
    if (iTemp mod idx = 0) then begin
      if (iCount > 0) and (Result[iCount-1].Base = idx) and (iCount <> 0) then begin
        inc(Result[iCount-1].Power);
      end else begin
        inc(iCount);
        SetLength(Result, iCount);
        Result[iCount-1].Base := idx;
        Result[iCount-1].Power := 1;
      end;
      iTemp := iTemp div idx;
    end else
      inc(idx);
  end;
end;
Zu Bemerken ist, dass diese Algorithmus relativ langsam ist und nur mit kleinen Zahlen arbeiten kann (Innerhalb der Grenzen von Longint).
Demo: http://downloads.csd-software.net/pf...ce_v01_src.zip

alzaimar hat noch eine alternative Brute-Force-Methode:
Delphi-Quellcode:
Procedure Factorize (aNumber : Integer);
Var
  p, aStop :Integer;
  f : Boolean;

  Procedure AddFactor (aFactor : Integer);
  Begin
    While (aNumber > 1) And (aNumber mod aFactor = 0) Do Begin
      form1.memo1.lines.add (IntToStr (aFactor));
      aNumber := aNumber div aFactor;
      aStop := Trunc (Sqrt (aNumber));
      End;
  End;

Begin
  AddFactor (2);
  AddFactor (3);
  p := 5; f := True;
  aStop := Trunc (Sqrt (aNumber));
  While p <= aStop do begin
    AddFactor (p);
    if f then inc (p,2) else inc (p,4);
    f := Not f;
    End;
  If aNumber > 1 then
    AddFactor (aNumber);
End;
Pollard-Rho-Methode
Die Pollard-Rho-Methode hat den großen Vorteil, dass sie extrem schnell ist. Jedoch nur unter der Vorraussetzung, dass die gewählte Zufallszahl passend ist. Denn die ganze Methode beruht im Grunde auf Zufallszahlen. Wichtig ist, dass man vor der Faktorierung einen Primzahltest durchführt, da ansonsten sich Pollard Rho in einer Endlosschleife verfängt. Es reicht jedoch einen Test durchzuführen, der zeigt, dass n keine Primzahl ist (es gibt spezielle Tests für diese Art des Primzahltests; zum Beispiel Primzahltest nach Fermat).
Ansonsten ist noch anzumerken, dass die Pollard-Rho-Methode nur einen ganzzahligen Faktor findet und dieser nicht unbedingt prim sein muss. D.h. um eine komplette Primfaktorzerlegung zu erhalten muss dieser Algorithmus mehrmals hintereinander durchgeführt werden.

Rest (u.a. Source) Folgt...
»Mein Kaffee ist so schwarz — der fängt gleich an zu rappen...«
  Mit Zitat antworten Zitat
Themen-Optionen Thema durchsuchen
Thema durchsuchen:

Erweiterte Suche
Ansicht

Forumregeln

Es ist dir nicht erlaubt, neue Themen zu verfassen.
Es ist dir nicht erlaubt, auf Beiträge zu antworten.
Es ist dir nicht erlaubt, Anhänge hochzuladen.
Es ist dir nicht erlaubt, deine Beiträge zu bearbeiten.

BB-Code ist an.
Smileys sind an.
[IMG] Code ist an.
HTML-Code ist aus.
Trackbacks are an
Pingbacks are an
Refbacks are aus

Gehe zu:

Impressum · AGB · Datenschutz · Nach oben
Alle Zeitangaben in WEZ +1. Es ist jetzt 23:47 Uhr.
Powered by vBulletin® Copyright ©2000 - 2019, Jelsoft Enterprises Ltd.
LinkBacks Enabled by vBSEO © 2011, Crawlability, Inc.
Delphi-PRAXiS (c) 2002 - 2019 by Daniel R. Wolf