Seite 2 von 2
Re: Primzahlengenerator
Verfasst: Mittwoch 28. Dezember 2016, 21:05
von bb1898
In der Generatorfunktion prim_teiler_ohne_modulo kann man auch noch die durch 3 teilbaren Zahlen aus der Prüfung herauslassen, allerdings wird die Schleife dann komplizierter:
Code: Alles auswählen
def prim_teiler_ohne_modulo():
yield 2
yield 3
primzahlen = list()
wurzel = 0
d = -1
zahl = 5
while True:
if not any(prim.teilbar(zahl) for prim in itertools.islice(primzahlen,
wurzel)):
primzahlen.append(PrimModulo(zahl))
wurzel = int(len(primzahlen) ** 0.5)
yield zahl
# Abwechselnd 2 und 4 zu zahl addieren
zahl += 3 + d
d = -d
Ich habe allerdings bisher gerade mal getestet, dass die Primzahlen bis 100 richtig ausgegeben werden, mehr noch nicht. Insbesondere habe ich keine Laufzeiten verglichen. Interessant wird das Verfahren ja aber eher für Fragestellungen wie "die ersten 100 Primzahlen finden" oder Ähnliches, ohne vorgegebene Obergrenze.
Re: Primzahlengenerator
Verfasst: Mittwoch 28. Dezember 2016, 22:22
von Sirius3
@bb1898: mit einer for-Schleife läßt sich das einfacher schreiben
Code: Alles auswählen
from itertools import islice, chain, count
try:
from itertools import izip
except ImportError:
izip = zip
def prim_teiler_ohne_modulo():
yield 2
yield 3
wurzel = 0
primzahlen = list()
for zahl in chain.from_iterable(izip([count(5, 6), count(7, 6)]):
if not any(prim.teilbar(zahl) for prim in islice(primzahlen, wurzel)):
primzahlen.append(PrimModulo(zahl))
wurzel = int(len(primzahlen) ** 0.5)
yield zahl
Re: Primzahlengenerator
Verfasst: Donnerstag 29. Dezember 2016, 02:06
von HarteWare
Hier gibts einen tollen Link zum Sieb des Eratosthenes:
https://prof.beuth-hochschule.de/filead ... thenes.pdf
Edit: Ups, da bin ich wohl etwas spät... Klassiker.
Re: Primzahlengenerator
Verfasst: Donnerstag 29. Dezember 2016, 14:10
von pyHoax
Ich hab da noch einen Lösung um die Quadratwurzel zu entfernen.
Die Folge der ganzahligen Wurzelwerte läßt sich aus einer Reihenformel herleiten ohne die Quadratwurzelfunktion zu zitieren.
Code: Alles auswählen
def prim_teiler_ohne_modulo_und_wurzel():
yield 2
primzahlen = list()
wurzel = 0
wurzel_grenze = 1
for zahl in count(3, 2):
if not any(prim.teilbar(zahl) for prim in islice(primzahlen, wurzel)):
primzahlen.append(PrimModulo(zahl))
if len(primzahlen) == wurzel_grenze:
wurzel += 1
wurzel_grenze += 2 * wurzel + 1
yield zahl
Re: Primzahlengenerator
Verfasst: Donnerstag 29. Dezember 2016, 15:28
von pyHoax
Der Primsieb ist auch bedeutend schneller solange das Sieb selber in den Speicherpasst.
Dies ist meine bisher schickste implementation des Siebes:
Code: Alles auswählen
def prim_sieb(n):
if n < 2:
return [2] if n == 2 else []
size = len(range(3, n + 1, 2))
sieb = bytearray([True]) * size
max_prim = int(n ** 0.5) + 1
for prim in compress(range(3, max_prim , 2), sieb):
start = (prim ** 2 - 3) // 2
sieb[start::prim] = bytearray([False]) * len(range(start, size, prim))
prime_numbers = [2]
prime_numbers.extend(compress(range(3, n + 1, 2), sieb))
return prime_numbers
Aussteht noch eine implementierung die als Generator funktioniert. Dazu muss aber erstmal eine Lösung zur Partitionierung des Siebes her.
Re: Primzahlengenerator
Verfasst: Donnerstag 29. Dezember 2016, 20:46
von bb1898
@sirius: In Deiner Zeile 12 stimmen die Klammern nicht ganz, so muss es aussehen:
Code: Alles auswählen
for zahl in chain.from_iterable(izip(count(5, 6), count(7, 6))):
Aber dann gefällt mir diese Schleife entschieden besser als meine Uralt-Variante (wirklich uralt, ich habe die ganze Idee aus einem Buch zu programmierbaren Taschenrechnern). Über itertools kann man gar nicht genug wissen. Danke schön!