Autor Beitrag
huuuuuh
ontopic starontopic starontopic starontopic starontopic starhalf ontopic starofftopic starofftopic star
Beiträge: 665
Erhaltene Danke: 19

win xp, (win vista), win 7
VS 2008 Express Edition, VS 2010 Express Edition, VS 2010 Professionell
BeitragVerfasst: 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
ausblenden 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
ontopic starontopic starontopic starontopic starontopic starontopic starofftopic starofftopic star
Beiträge: 8548
Erhaltene Danke: 477

Windows 7, Windows 10
D7 PE, Delphi XE3 Prof, Delphi 10.3 CE
BeitragVerfasst: 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 Threadstarter
ontopic starontopic starontopic starontopic starontopic starhalf ontopic starofftopic starofftopic star
Beiträge: 665
Erhaltene Danke: 19

win xp, (win vista), win 7
VS 2008 Express Edition, VS 2010 Express Edition, VS 2010 Professionell
BeitragVerfasst: 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
ontopic starontopic starontopic starontopic starontopic starontopic starofftopic starofftopic star
Beiträge: 8548
Erhaltene Danke: 477

Windows 7, Windows 10
D7 PE, Delphi XE3 Prof, Delphi 10.3 CE
BeitragVerfasst: 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 Threadstarter
ontopic starontopic starontopic starontopic starontopic starhalf ontopic starofftopic starofftopic star
Beiträge: 665
Erhaltene Danke: 19

win xp, (win vista), win 7
VS 2008 Express Edition, VS 2010 Express Edition, VS 2010 Professionell
BeitragVerfasst: 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
ontopic starontopic starontopic starontopic starontopic starontopic starhalf ontopic starofftopic star
Beiträge: 1097
Erhaltene Danke: 2



BeitragVerfasst: 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 Threadstarter
ontopic starontopic starontopic starontopic starontopic starhalf ontopic starofftopic starofftopic star
Beiträge: 665
Erhaltene Danke: 19

win xp, (win vista), win 7
VS 2008 Express Edition, VS 2010 Express Edition, VS 2010 Professionell
BeitragVerfasst: Mi 11.06.08 16:39 
ok...jetz krieg ich ne access violation...
ausblenden Delphi-Quelltext
1:
pzl.Add('1');					
alzaimar
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starofftopic star
Beiträge: 2889
Erhaltene Danke: 13

W2000, XP
D6E, BDS2006A, DevExpress
BeitragVerfasst: 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 Threadstarter
ontopic starontopic starontopic starontopic starontopic starhalf ontopic starofftopic starofftopic star
Beiträge: 665
Erhaltene Danke: 19

win xp, (win vista), win 7
VS 2008 Express Edition, VS 2010 Express Edition, VS 2010 Professionell
BeitragVerfasst: Mi 11.06.08 17:10 
so problem jetz behoben
10sek. jetz^^
Yogu
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starhalf ontopic star
Beiträge: 2598
Erhaltene Danke: 156

Ubuntu 13.04, Win 7
C# (VS 2013)
BeitragVerfasst: 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
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starofftopic star
Beiträge: 2889
Erhaltene Danke: 13

W2000, XP
D6E, BDS2006A, DevExpress
BeitragVerfasst: 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



BeitragVerfasst: 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 Threadstarter
ontopic starontopic starontopic starontopic starontopic starhalf ontopic starofftopic starofftopic star
Beiträge: 665
Erhaltene Danke: 19

win xp, (win vista), win 7
VS 2008 Express Edition, VS 2010 Express Edition, VS 2010 Professionell
BeitragVerfasst: 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.
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starofftopic star
Beiträge: 554

Windows 7 Ultimate
Visual Studio 2008 Pro, Visual Studion 2010 Ultimate
BeitragVerfasst: 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.