Generatoren "lesen"

[pychart]

Hallo liebe Community,
als ich auf der Suche nach "Primzahlen mit Python erzeugen" war, bin ich auf folgenden Code gestoßen:

Code: Alles auswählen

# Sieve of Eratosthenes
# Code by David Eppstein, UC Irvine, 28 Feb 2002
# http://code.activestate.com/recipes/117119/

def gen_primes():
    """ Generate an infinite sequence of prime numbers.
    """
    # Maps composites to primes witnessing their compositeness.
    # This is memory efficient, as the sieve is not "run forward"
    # indefinitely, but only as long as required by the current
    # number being tested.
    #
    D = {}
    
    # The running integer that's checked for primeness
    q = 2
    
    while True:
        if q not in D:
            # q is a new prime.
            # Yield it and mark its first multiple that isn't
            # already marked in previous iterations
            # 
            yield q
            D[q * q] = [q]
        else:
            # q is composite. D[q] is the list of primes that
            # divide it. Since we've reached q, we no longer
            # need it in the map, but we'll mark the next 
            # multiples of its witnesses to prepare for larger
            # numbers
            # 
            for p in D[q]:
                D.setdefault(p + q, []).append(p)
            del D[q]
        
        q += 1

Das Problem ist aber, dass ich nicht weiß, wie man diesen Code ausführt, sodass ich am Ende meine Primzahlen printen kann :K . Als ich recherchiert habe, stieß ich auf Generatoren etc., wobei ich da nicht ganz durchblicke. Vielen Dank im Voraus.

[olfibits]

Schreib doch deinen Generator selber.

Ansatz:
for-Schleife 1-100 (100 eventuell eine Variable) und immer hochzählen. Wenn es eine Primzahl ist (nicht durch 2, 3, 5, 7 teilbar), ausgeben mit print()

[__deets__]

Generatoren generieren - wie ihr Name schon sagt - Werte. Ein beliebter Generator den du kennen solltest ist range (bzw xrange fuer Python 2). Und so musst du das hier auch nutzen: einfach mit for drueber iterieren, bis du genug hast.

[noisefloor]

Hallo,

was blickst du denn genau nicht? Du bindest die Funktion an eine Variable, und rufst dann `next(name_der_funktion)` auf. Der Rückgabewert ist dann eine Primzahl.

Oder direkt drüber iterieren, wie von __deets__ gesagt.

Gruß, noisefloor

[narpfel]

Moin,

`gen_primes` ist eine Generatorfunktion. Generatorfunktionen geben einen Generator zurück, wenn man sie aufruft. Und Generatoren implementieren das Iterator-Protokoll. (Das sind die relevanten Stichworte, falls du dazu weitere Informationen suchst.)

Das einzige, was man mit Iteratoren machen kann, ist über sie zu iterieren. Das kann man beispielsweise mit einer `for`-Schleife machen, oder indem man sie an `list` übergibt: `list(gen_primes())` erzeugt eine Liste aller Primzahlen (dauert natürlich ein wenig...). Außerdem ist das `itertools`-Modul hilfreich, um mit Iteratoren zu arbeiten. Insbesondere `islice` und `takewhile` könnten interessant sein, um aus dem unendlichen Iterator einen endlichen zu machen (natürlich kann man auch eine `for`-Schleife nehmen, die bei einer bestimmten Bedingung mit `break` verlassen wird).

[pychart]

Danke für die Antworten, bin nicht recht firm in Python. Also der Ansatz mit der For-Schleife, soll der so aussehen:

Code: Alles auswählen

for x in range(0,20):
		gen_primes()

Oder könnte mir jemand ein konkretes Beispiel geben bitte, wie ich drüber iteriere.

EDIT:

Code: Alles auswählen

for x in gen_primes():
    print(x)

Das klappt! Ist das richtig so?

[__deets__]

Wie ich schon schrieb: range *ist* ein generator. Und du hast einen generator. Wenn das beides Generatoren sind, dann kann man dein Beispiel lauffaehig bekommen, wenn du range mit deinem generator ersetzt. Und natuerlich x ausgibst.

[pychart]

Hat geklappt, vielen Dank!!

[Sirius3]

Zur Vollständigkeit, den Code noch ins Jahr 2018 gehievt:

Code: Alles auswählen

from collections import defaultdict
def generate_primes():
    """ Generate an infinite sequence of prime numbers.
    """
    # Maps composites to primes witnessing their compositeness.
    # This is memory efficient, as the sieve is not "run forward"
    # indefinitely, but only as long as required by the current
    # number being tested.
    yield 2
    
    sieve = defaultdict(list)
    number = 3
    while True:
        if number not in sieve:
            # number is a new prime.
            # Yield it and mark its first multiple that isn't
            # already marked in previous iterations
            yield number
            sieve[number * number] = [number]
        else:
            # number is composite. sieve[number] is the list of primes that
            # divide it. Since we've reached number, we no longer
            # need it in the map, but we'll mark the next 
            # multiples of its witnesses to prepare for larger
            # numbers
            for p in sieve.pop(number):
                sieve[number + 2*p].append(p)
        number += 2

Problem ist, dass irgendwann der Speicher vollläuft.