Welcome, guest | Sign In | My Account | Store | Cart

Simple prime generator.

I write it as a sample usage of the any function.

Python, 27 lines
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
"""
    Prime number generator

I found it quite simple to implement this generator with the 'any' function
It is certainly not the most optimized algorithm.
Primes list will only grow in the function though.

"""
import itertools

def primes():
    """Simple prime numbers generator

    >>> [prime for prime, index in zip(primes(), range(10))]
    [1, 2, 3, 5, 7, 11, 13, 17, 19, 23]
    """
    yield 1
    primes = []
    for n in itertools.count(2):
        if not any(n % p == 0 for p in primes):
            # No divisor found among previous primes
            yield n
            primes.append(n)
    
if __name__ == "__main__":
    import doctest
    doctest.testmod()

Hello,

I didn't found generator like this as recipe, and it was a good start to subscribe to this great cookbook site.

Do you see any improvement directions? Cheers.

6 comments

Maxime Fontenier (author) 14 years, 4 months ago  # | flag

Thanks. I hadn't read the full comments of this recipe.

Thomas Ahle 14 years, 4 months ago  # | flag

Please, 1 is not a prime!! Any number > 1 can be factorized uniquely into primes. How can this be true if two can be written as 2 or 21 or 21*1...

Other than that, it is a fine example on Sieve of Eratosthenes. It is a bit misleading to use a generator though, as the function grows in RAM use proportional (or a bit faster) to the number of primes received.

As a last comment, the [prime for prime, index in zip(primes(), range(10))] line could usefully be replaced with itertools.islice(primes(),10) or list(itertools.islice(primes(),10))

Didier Villers 14 years, 4 months ago  # | flag

There is also this program http://code.activestate.com/recipes/576640/ which has the "prime" tag

Rodney Drenth 14 years, 4 months ago  # | flag

Two comments - First, 1 is not considered a prime by mathematicians. Secondly, after 2, you only really have to check odd numbers for primeality

Maxime Fontenier (author) 14 years, 4 months ago  # | flag

Thanks! http://code.activestate.com/recipes/576640/ is exactly what I was aiming at.