Autor |
Beitrag |
huuuuuh
      
Beiträge: 665
Erhaltene Danke: 19
win xp, (win vista), win 7
VS 2008 Express Edition, VS 2010 Express Edition, VS 2010 Professionell
|
Verfasst: Mi 11.06.08 15:54
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
      
Beiträge: 8548
Erhaltene Danke: 477
Windows 7, Windows 10
D7 PE, Delphi XE3 Prof, Delphi 10.3 CE
|
Verfasst: 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.
_________________ We are, we were and will not be.
|
|
huuuuuh 
      
Beiträge: 665
Erhaltene Danke: 19
win xp, (win vista), win 7
VS 2008 Express Edition, VS 2010 Express Edition, VS 2010 Professionell
|
Verfasst: 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
aber das mit der wurzel wusst ich nich...warum funktioniert das? muss ich ma drüber nachdenken....
|
|
Gausi
      
Beiträge: 8548
Erhaltene Danke: 477
Windows 7, Windows 10
D7 PE, Delphi XE3 Prof, Delphi 10.3 CE
|
Verfasst: 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. 
_________________ We are, we were and will not be.
|
|
huuuuuh 
      
Beiträge: 665
Erhaltene Danke: 19
win xp, (win vista), win 7
VS 2008 Express Edition, VS 2010 Express Edition, VS 2010 Professionell
|
Verfasst: 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
      
Beiträge: 1097
Erhaltene Danke: 2
|
Verfasst: 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 
      
Beiträge: 665
Erhaltene Danke: 19
win xp, (win vista), win 7
VS 2008 Express Edition, VS 2010 Express Edition, VS 2010 Professionell
|
Verfasst: Mi 11.06.08 16:39
ok...jetz krieg ich ne access violation...
Delphi-Quelltext
|
|
alzaimar
      
Beiträge: 2889
Erhaltene Danke: 13
W2000, XP
D6E, BDS2006A, DevExpress
|
Verfasst: 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...
_________________ Na denn, dann. Bis dann, denn.
|
|
huuuuuh 
      
Beiträge: 665
Erhaltene Danke: 19
win xp, (win vista), win 7
VS 2008 Express Edition, VS 2010 Express Edition, VS 2010 Professionell
|
Verfasst: Mi 11.06.08 17:10
so problem jetz behoben
10sek. jetz^^
|
|
Yogu
      
Beiträge: 2598
Erhaltene Danke: 156
Ubuntu 13.04, Win 7
C# (VS 2013)
|
Verfasst: 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
      
Beiträge: 2889
Erhaltene Danke: 13
W2000, XP
D6E, BDS2006A, DevExpress
|
Verfasst: Mi 11.06.08 18:51
Wir hatten das vor einer Weile schonmal hier. Bei Interesse einfach mal die Suchfunkton bemühen.
_________________ Na denn, dann. Bis dann, denn.
|
|
Grenzgaenger
Ehemaliges Mitglied
Erhaltene Danke: 1
|
Verfasst: 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 
      
Beiträge: 665
Erhaltene Danke: 19
win xp, (win vista), win 7
VS 2008 Express Edition, VS 2010 Express Edition, VS 2010 Professionell
|
Verfasst: 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.
      
Beiträge: 554
Windows 7 Ultimate
Visual Studio 2008 Pro, Visual Studion 2010 Ultimate
|
Verfasst: 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.
|
|