Search code examples
pythongeneratorinfinite-loop

How can I make an infinite generator in Python to all prime numbers?


I was trying to make this infinite generator in Python:

import math
def all_primes():
    count = 2
    while True:
        flag = True
        for x in range(2, int(math.sqrt(count) + 1)):
            if count % x == 0:
                flag = False

        if flag:
            yield count
        else:
            count += 1

for i in all_primes():
    print(i)

but in the output it always gives me 2. Why is that?


Solution

  • You don't augment count after finding a prime, so you're always returning the same value (3).

    Your prime generator is going to take longer and longer between each prime as you move forward.

    Here's an infinite prime generator that is more efficient. It is inspired from the sieve of Eratosthenes, but it uses a dictionary to only propagate multiples as it reaches a non-prime number and moves the prime multiple to the next multiple that hasn't been flagged as non-prime yet:

    def genPrimes():
        yield 2                      # get the first prime out of the way
        skips      = dict()          # multiples to skip {Multiple:2xPrime}
        multiples  = ((p*p,2*p) for p in genPrimes()) # multiples of primes
        skipMark,_ = next(multiples)                  # skipping coverage
        N = 1                        # prime candidate (odd numbers)
        while True:
           N += 2                        # next prime candidate
           if N >= skipMark:                     # extend skips coverage
               skipMark,stride = next(multiples) # 1st multiple and stride
               skips[skipMark] = stride
           if N in skips:                # not a prime (multiple of a prime)
               stride   = skips.pop(N)   # get prime multiple steps
               multiple = N + stride     # advance skip to next multiple
               while multiple in skips:
                   multiple += stride    # not already skipped
               skips[multiple] = stride
           else:                         # N is prime
               yield N                   # return it
    

    Output:

    for p in genPrimes(): print(p)
    
    2
    3
    5
    7
    11
    13
    17
    19
    23
    29
    31
    37
    41
    43
    47
    53
    59
    ...
    

    The skips dictionary contains roughly one entry per √P (where P is the number of primes found so far) and doesn't require pre-allocating memory. This approach trades space for a gain in time.