Entwickler-Ecke

Algorithmen, Optimierung und Assembler - Primzahlenberechnung


huuuuuh - Mi 11.06.08 15:54
Titel: Primzahlenberechnung
ich hab ein programm geschrieben für die berechnung von primzahlen - funktioniert auch...
ich würd gern wissen ob das schneller geht und wie...
hier mein code

Delphi-Quelltext
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
zahl:=0;
i:=100;
 repeat
  inc(zahl);
  teiler:=2;
  primzahl:=true;
   repeat
    if (zahl/teiler) = (trunc(zahl/teiler)) then primzahl:=false;
    inc(teiler);
   until (primzahl=false) or (teiler>(zahl/2));
  if (primzahl) or (zahl=teiler-1then listbox1.items.Add(inttostr(zahl));
  if listbox1.items.count=i then
   begin
    try listbox1.Items.SaveToFile('C:\primzahlen.txt');
    except
    end;
    i:=i+100;
   end;
 until listbox1.Items.count=strtoint(edit1.text);

funktionalität sollte erhalten bleiben (also primzahlen speichern alle 100 primzahlen)


Moderiert von user profile iconChristian S.: Topic aus Sonstiges (Delphi) verschoben am Mi 11.06.2008 um 15:55


Gausi - Mi 11.06.08 15:59

Ganz einfache Beschleunigung: anstelle von zahl/2 einfach sqrt(zahl) als Grenze für den Test wählen. Das reicht auch. Und zahl könntest du auch bei 3 starten lassen, und nur jede zweite zahl testen. Gerade Zahlen sind nur äußerst selten Primzahlen. ;-)

Das sind zwei ganz einfache Verbesserungen.


huuuuuh - Mi 11.06.08 16:08

ok, auf das jede 2. zahl testen hätt ich auch selber kommen können...irgendwie isses recht einleuchtend :oops:
aber das mit der wurzel wusst ich nich...warum funktioniert das? muss ich ma drüber nachdenken....


Gausi - Mi 11.06.08 16:15

Wenn x = a*b gilt, dann ist a <= Wurzel(x) oder b <= Wurzel(x). Wenn du also alle Zahlen bis Wurzel(x) als Teiler ausgeschlossen hast, dann reicht das. ;-)


huuuuuh - Mi 11.06.08 16:21

ok...ich verstehs...
kaum zu glauben...diese beiden veränderungen haben die suche nach 100000 primzahlen von ca. 20 min auf ca. 1 min verkürzt...das dürfte reichen
danke dir


Chryzler - Mi 11.06.08 16:27

Um einiges schneller sollte es auch gehen, wenn du anstatt der ListBox1.Items eine TStringList nimmst, ohne die Zahlen anzuzeigen. Mein Primzahlprogramm braucht für alle Primzahlen bis 100000 0,02 Sek., und das ist sicherlich ned besonders optimiert.


huuuuuh - Mi 11.06.08 16:39

ok...jetz krieg ich ne access violation...

Delphi-Quelltext
1:
pzl.Add('1');                    


alzaimar - Mi 11.06.08 16:45

Noch ein Tipp: Alle Primzahlen >3 sind von der Form '6*n +/-1'. Du könntest also die zu prüfende Zahl ausgehend von 5 erst mit 2, und dann mit 4 addieren. Spart nochmal ein bisserl Zeit.

Richtig spaßig wird es aber mit em ' Sieb des Eratosthenes', such mal hier oder in der delphi-Praxis danach...


huuuuuh - Mi 11.06.08 17:10

so problem jetz behoben
10sek. jetz^^


Yogu - Mi 11.06.08 18:08

Ich mach mal weiter...

Wenn du sehr große Primzahlen berechnen willst, hilft es, nur die bereits berechneten Primzahlen als Teiler zu nehmen. Du kannst sie in einem array of Cardinal speichern und für jede neue Primzahl alle durchgehen. Wenn du durch keine Primzahl teilen kannst, geht das auch nicht mit anderen Zahlen.

Vielleicht hilft auch Assembler, aber ich glaube, Delphi compiliert da schon ganz gut.

Grüße,
Yogu


alzaimar - Mi 11.06.08 18:51

Wir hatten das vor einer Weile schonmal hier. Bei Interesse einfach mal die Suchfunkton bemühen.


Delete - Mi 11.06.08 20:16

hast hier schon mal die SuFu verwendet? hier gibts mind. 20 thread mit hochoptimierten code zum finden von primzahlen :-)


huuuuuh - Do 12.06.08 15:42

user profile iconYogu hat folgendes geschrieben:
Ich mach mal weiter...

Wenn du sehr große Primzahlen berechnen willst, hilft es, nur die bereits berechneten Primzahlen als Teiler zu nehmen. Du kannst sie in einem array of Cardinal speichern und für jede neue Primzahl alle durchgehen. Wenn du durch keine Primzahl teilen kannst, geht das auch nicht mit anderen Zahlen.

Vielleicht hilft auch Assembler, aber ich glaube, Delphi compiliert da schon ganz gut.

Grüße,
Yogu


werd ma sehn. welcher zahlendatentyp kann denn die größten zahlen beinhalten?


Fabian E. - Do 12.06.08 16:02

Du kannst Int64 nehmen. Wenn du was noch größeres willst kannst du dich ja mal nach sog. "BigIntUnits" umsehen.