ActiveState Code

Recipe 576948: Simple primes generator

Simple prime generator.

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

Python 
 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()

Discussion

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.

Comments

  1. 1. At 8:10 a.m. on 4 nov 2009, Matteo Dell'Amico said:

    http://code.activestate.com/recipes/117119/

  2. 2. At 9:26 a.m. on 4 nov 2009, Maxime Fontenier (the author) said:

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

  3. 3. At 7:20 a.m. on 7 nov 2009, Thomas Ahle said:

    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))

  4. 4. At 9:17 a.m. on 7 nov 2009, Didier Villers said:

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

  5. 5. At 1:10 p.m. on 16 nov 2009, Rodney Drenth said:

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

  6. 6. At 2:27 p.m. on 17 nov 2009, Maxime Fontenier (the author) said:

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

Sign in to comment