Programm Optimierung

[DeathsShadow]

Hi ihr :hi: ,

Ich habe ein Programm zum Herausfiltern von Primzahlen geschrieben :coder: . Allerdings ist dieses recht langsam und ich wollte mal fragen, ob irgendjemand eine Idee hat, wie ich dieses Programm zu Gunsten der Geschwindigkeit verändern bzw. optimieren kann. :?:

Hier der Code:

Delphi-Quellcode:

unit Primzahlen_Generator;

interface

uses ExtCtrls, Math, SysUtils, Classes;

type
  TPrimzahlen_Generator = class

  private
    A_Zahlen : Array of Integer;
    Zahlengrenze : Integer;

  private
    procedure Filtern (Panel: TPanel; Grenze : Integer); virtual;
    procedure Loeschen_Aufruecken (Pos: Integer); virtual;
    procedure Speichern (Speicherort: String); virtual;
    procedure Werte_Uebernehmen (Grenze: Integer); virtual;

  public
    procedure Ausfuehren (Grenze: Integer; Speicherort: String; Anzeigepanel: TPanel); virtual;

   end;

implementation

procedure TPrimzahlen_Generator.Filtern (Panel: TPanel;Grenze : Integer);
var i, j : Integer;
begin
  for j := 2 to round(power(Grenze+1,1/2)) do
  begin
    for i := Length(A_Zahlen)-1 downto j-1 do
    begin
      if (A_Zahlen[i] mod j = 0) and (A_Zahlen[i] <> j) then Loeschen_Aufruecken(i);
      if i mod 100 = 0 then
      begin
        Panel.Caption := 'Noch: '+inttostr(round(power(Length(A_Zahlen)-1,1/2)+1)-j);
        Panel.Update;
      end;
    end;
  end;
  Panel.Caption := 'Fertig!';
end;

procedure TPrimzahlen_Generator.Loeschen_Aufruecken (Pos: Integer);
var i : Integer;
begin
  for i := pos to length(A_Zahlen)-2 do
  begin
    A_Zahlen[i] := A_Zahlen[i+1];
  end;
  setlength(A_Zahlen,length(A_Zahlen)-1);
end;

procedure TPrimzahlen_Generator.Speichern (Speicherort: String);
var
    Datei: TextFile;
    i : Integer;
begin
  AssignFile(Datei, Speicherort + 'Primzahlen von 2 bis '+inttostr(Zahlengrenze)+'.txt');
  Rewrite(Datei);
  try
    WriteLn(Datei,inttostr(Length(A_Zahlen)));
    for i := 0 to Length(A_Zahlen)-1 do
    begin
    WriteLn(Datei,inttostr(i)+' - '+inttostr(A_Zahlen[i]) );
    end;
  finally
    CloseFile(Datei);
  end;
end;

procedure TPrimzahlen_Generator.Werte_Uebernehmen (Grenze: Integer);
var i : Integer;
begin
  setlength(A_Zahlen,Grenze-1);
  for i := 2 to length(A_Zahlen)-1 do
  begin
    A_Zahlen[i-2] := i;
  end;
Zahlengrenze := Grenze;
end;

procedure TPrimzahlen_Generator.Ausfuehren (Grenze: Integer; Speicherort: String; Anzeigepanel: TPanel);
begin
  Werte_Uebernehmen(Grenze);
  Filtern(Anzeigepanel,Grenze);
  Speichern(Speicherort);
end;

end.

_______________
Lg Florian :bounce2:

[mkinzler]

Ein mathematisches Verfahren zur Primfaktorenzerlegung sollte da deutlich schneller sein
[Edit: Tippfehler entfernt]

[WInfo]

Moin Moin Florian,

wollte mal darauf hinweisen, dass es in den Foren eine SuFu gibt, wo man z. B. auf folgenden Link stößt. Hier kann man sich prima Anregungen hohlen.

[jfheins]

Ich würde sagen: Trenne den Code von der Darstellung.

Du benutzt so was ähnliches wie das Sieb des Eratosthenes - aber warum nur so ähnlich?

Du möchtest alle Primzahlen von 0 bis X finden ?

Dann erstelle dir ein dyn. Array of Boolean mit der Länge X + 1.

Dort setzt du alle Werte erstmal auf true (true heißt später Primzahl, false keine Primzahl) nur den Eintrag 0 und 1 auf false (per Def. keine Primzahl)

Dann gehst du das Array durch, und zwar streichst du alle vielfachen der 2 weg, und gehst dann zur nächsten, nicht weggestrichenen Zahl:

Code:

var
  i, j: Integer;

for i := 2 to sqrt(X) do // Es gibt eine Fkt. sqrt() statt power(...)
begin
  if not arr[i] then continue;

  j := i * 2;
  while  j <= X do
  begin
    arr[j] := false;
    j := j + i;
  end;
end;

Im Anschluss kannst du dann alle Primzahlen (die, bei denen arr[y] true ist) ausgeben ;)

[DeathsShadow]

Vielen Danke für die schnellen Antworten, ich werde es ausprobieren :thumb:

[3_of_8]

Ich würde das mit einem Bitvektor machen. Der Vorteil: Verringerung des Speicherverbrauchs um den Faktor 32 (oder 8, ich kann mir nie merken, wie Boolean-Arrays jetzt genau aussehen)

[DeathsShadow]

was ist denn "Bitvektor" ... ich habe mal im inet geguckt und kein tutorial oder ähnliches gefunden.

[mkinzler]

Statt einer Variable nimmt man ein Bit einer variable. Die man dann durch Ausmaskieren abprüfen kann

[SirThornberry]

Ich denke er meint einfach nur das er kein Array of Boolean nehmen würde sondern einfach bits setzen damit somit für jede Zahl nur ein bit benötigt.

[3_of_8]

Ja, genau das meine ich. Delphi stellt dafür sogar eine Klasse zur Verfügung: TBits

Also wenn immer man eine große Anzahl an true/false-Werten verwalten sind, sind Bitvektoren eine mögliche, speichersparende Alternative zu Boolean-Arrays mit geringem Mehraufwand an Performance.

[taaktaak]

Bei den heutigen typischen Speichergrößen aber wohl nur bei sehr große Datenmengen relevant.
Mit

Zitat:

mit geringem Mehraufwand an Performance

meinst du sicherlich "geringe Minderung der Performance" - oder?

[Noedel]

muss das denn so kompliziert sein? ich dachte immer, man könne eine Primzahl daran erkennen, dass sie nur 2 teiler hat?!
Oder ist diese Lösung sehr langsam?

Delphi-Quellcode:

ZuUntersuchenderWert:=StrToInt(EUntergrenze.Text);
Obergrenze:=StrToInt(EObergrenze.Text);
REPEAT
  anzahlTeiler:=0;
  FOR i:=2 to ZuUntersuchenderWert-1 DO
      IF (ZuUntersuchenderWert mod i = 0)  THEN inc(anzahlTeiler);
  IF (anzahlTeiler=0) and (ZuUntersuchenderWert>=2)THEN Listbox1.Items.Add(InTtoStr(ZuUntersuchenderWert));
  inc(a);
UNTIL ZuUntersuchenderWert=Obergrenze;

[Namenloser]

Zitat:

Zitat von Noedel

Oder ist diese Lösung sehr langsam?

Ja. Das Sieb des Erasthotenes ist jedenfalls schneller...

[3_of_8]

Kommt darauf an, was man machen will: Wenn man nur eine Primzahl überprüfen will, ist diese Methode auf jeden Fall schneller. Wenn man aber Primzahlen finden will, ist das Sieb des Erathostenes schneller - dafür hat es einen deutlich höheren Speicherverbrauch hat.

[Namenloser]

Zitat:

Zitat von 3_of_8

Wenn man nur eine Primzahl überprüfen will, ist diese Methode auf jeden Fall schneller.

Es sei denn man hätte schon ein generiertes Sieb :wink: