Pythonic Prime Generation

Question

I am using a sieve to return all primes under N:

def prime_gen(n):
    a = [x for x in range(2, n+1)]
    for b in range(2, round(n**.5)):
        c = 2
        while b*c <= n:
            if b*c in a:
                a.remove(b*c)
            c += 1
    return(a)

Is the conditional if b*c in a iterating through the list again? Without using a different algorithm entirely, how do I make this code more efficient and pythonic?

Answer 1

Use Python's math library

You can either import the whole math library, or just import the modules you need.

from math import sqrt, floor

Use a dictionary instead of a list

Yes, if b*c in a iterates through the list. However, if you use a dictionary, it takes only a single operation to look up any value. This is because Python stores dictionary keys and values as a hash table.

You can use Python's dict comprehension syntax.

d = {key: value for (key, value) in iterable}

The result looks like this:

from math import sqrt, floor

def prime_gen(n):
    a = {k: 0 for k in range(2, n+1)}
    for b in range(2, floor(sqrt(n))):
        c = 2
        while b*c <= n:
            if b*c in a:
                a.remove(b*c)
            c += 1
    return(a)

Answer 2

It's pretty code, but you could make it more efficient. For example, you're iterating through all the values from 2 to sqrt(n). Can you iterate through only the prime ones? Take a look at the Sieve of Eratosthenes for more inspiration. Furthermore, I believe that if you stuck the remove statement into a Try block instead of an if statement, it would only have to search the space twice.