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.