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-1) then 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
Christian 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...
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
Yogu 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.
Entwickler-Ecke.de based on phpBB
Copyright 2002 - 2011 by Tino Teuber, Copyright 2011 - 2025 by Christian Stelzmann Alle Rechte vorbehalten.
Alle Beiträge stammen von dritten Personen und dürfen geltendes Recht nicht verletzen.
Entwickler-Ecke und die zugehörigen Webseiten distanzieren sich ausdrücklich von Fremdinhalten jeglicher Art!