Primzahlengenerator

[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.

[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

[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.

[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

[pyHoax]

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.

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.

[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!