DEV Community

Infinite list of prime numbers using Python generators

Alejandro Bezdjian on September 14, 2019

Sometimes we want to create collections of elements that are very expensive to calculate. The first option is to create a list and wait until all t...

Read full post

orenovadia • Sep 16 '19

Since the time complexity of is_prime is O(sqrt(n)):
Worth a mention that for prime numbers up to N, overall, using this method is not as time efficient as sieve methods that eagerly pre-calculate all the primes up to N (this is because sieves use previously found primes to eliminate other composite numbers, instead of performing an exhaustive search for each number).

Rishit Chaudhary • Sep 10 '20

Hi,
Amazing post. It's a really great example to understand how to use generators in Python!

I feel the code above can be improved a bit further, by starting the check for prime numbers from a more suitable number, hence the primeGenerator() method can be rewritten as follows

def primeGenerator():
    n = 3
    while True:
        if isPrime(n):
            yield n
        n += 1

Alejandro Bezdjian • Sep 14 '20

Hi! I’m glad you liked it! The snippet you provided should start from the number 2 because it is also a prime number.

Rishit Chaudhary • Sep 14 '20

Yeah, your absolutely right!
I guess my previous snippet would only be useful for people wanting to print all prime numbers except the even prime number (which is 2).

Here is my corrected code, which gives all the prime numbers:

def primeGenerator():
    n = 2
    while True:
        if isPrime(n):
            yield n
        n += 1

Thank You,
Rishit

Billy Einkamerer • May 28 '21 • Edited

Thanks for this - it was super helpful.
I hacked it a bit and added a value limit for the prime number check, so that you can check the prime numbers up to X.

Changed up the prime generator function to have a limit (also set a default limit):

then used that limit in the call of the generator into a list:

so no longer need itertools and islice.

Alejandro Bezdjian • May 29 '21

I’m glad that you find it useful 🙂

Frank • Nov 9 '19

Nice post but 2 is not prime. You need to shift the n==2 if-statement to the top.

Alejandro Bezdjian • Nov 10 '19

Hi Frank, I’m afraid 2 is a prime number

Frank • Nov 10 '19

Hi Alejandro, yes, 2 is prime but your code says no.

Bwillis • Apr 18 '20

The code returns True if it is a prime number. It says if n == 2, return True, which states that 2 is a prime number, because it is actually a prime number

Jovan Cosovic • Aug 5 '20

Can u help me with describing the part of the code below i = 3?
Thanks.

Alejandro Bezdjian • Aug 7 '20

Hi Jovan, the first ifs in the code cover the cases where i <= 1 and i == 2, so starting the iteration with i = 1 will repeat the first 2 cases. It's just a minimum performance improvement.