mogbo
Banned
Hallo,
Tool 1 ("schnell") (time ./a.out 10000000 > test.txt | 5.4 sec)
Tool 2 ("langsam") (time ./a.out 10000000 > test.txt | 22.36 sec)
Kein schöner Code, ist nicht lesenswert (nur zum Testen aufgebaut). Wenn x ein vielfaches von 6 ist und x + 1 Prim, ist auch die Ausgabe buggy
beide Tools sind nicht kommentiert, haben jedoch folgende Funktionsweise:
Sie geben alle Primzahlen bis x aus (x max UINT_MAX). Die Zahlen 2 und 3 (ggf. 5) werden einfach ausgegeben, dann startet eine for() - Schleife:
jedes Vielfache von 6 wird einmal +1 und einmal -1 auf Primzahl geprüft.
- Der schnelle Algorithmus baut einen buffer mit Primzahlen auf und testet die Teiler der Testzahl nur mit Primzahlen im buffer (<= sqrt der geprüften Zahl)
- Der langsame Algorithmus macht dies ohne buffer und prüft einfach gegen jegliche ungerade Zahl > 5 (bis sqrt der geprüften Zahl)
Hat jemand eine Idee wie ich die Geschichte performanter gestalten kann ohne einen Sieb des Eratosthenes zu verbauen?
- Gibt es bessere alternativen zu x % y == 0
- kann ich die for()-Schleife performant verschlanken? (p*p - 1) % 24 == 0 ist zB. keine Alternative, da p * p sehr viel Performance kostet
EDIT: links geändert, da nicht read_only
free() call vergessen im Tool 1
Tool 1 ("schnell") (time ./a.out 10000000 > test.txt | 5.4 sec)
Tool 2 ("langsam") (time ./a.out 10000000 > test.txt | 22.36 sec)
Kein schöner Code, ist nicht lesenswert (nur zum Testen aufgebaut). Wenn x ein vielfaches von 6 ist und x + 1 Prim, ist auch die Ausgabe buggy
beide Tools sind nicht kommentiert, haben jedoch folgende Funktionsweise:
Sie geben alle Primzahlen bis x aus (x max UINT_MAX). Die Zahlen 2 und 3 (ggf. 5) werden einfach ausgegeben, dann startet eine for() - Schleife:
jedes Vielfache von 6 wird einmal +1 und einmal -1 auf Primzahl geprüft.
- Der schnelle Algorithmus baut einen buffer mit Primzahlen auf und testet die Teiler der Testzahl nur mit Primzahlen im buffer (<= sqrt der geprüften Zahl)
- Der langsame Algorithmus macht dies ohne buffer und prüft einfach gegen jegliche ungerade Zahl > 5 (bis sqrt der geprüften Zahl)
Hat jemand eine Idee wie ich die Geschichte performanter gestalten kann ohne einen Sieb des Eratosthenes zu verbauen?
- Gibt es bessere alternativen zu x % y == 0
- kann ich die for()-Schleife performant verschlanken? (p*p - 1) % 24 == 0 ist zB. keine Alternative, da p * p sehr viel Performance kostet
EDIT: links geändert, da nicht read_only
free() call vergessen im Tool 1
Zuletzt bearbeitet: