# Pythonic Prime Generation

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?

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


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.