Sieve of Eratosthenes in Python

Question

I am trying to write a python function to return the number of primes less than a given value and the values of all the primes. I need to use the Sieve of Eratosthenes algorithm. I believe I'm missing something in the function - For example, when I want to find the primes under 100. All I got is 2, 3, 5, 7. I am aware that if I don't use "square root", I can get all the primes I need; but I am told that I need to include square root there. Can someone please take a look at my code and let me know what I am missing? Thanks for your time.

def p(n):
is_p=[False]*2 + [True]*(n-1)
for i in range(2, int(n**0.5)):
    if is_p[i]:
        yield i
        for j in range(i*i, n, i):
            is_p[j] = False

Answer 1

"I am told I need to use square root". Why do you think that is? Usually the sieve of E. is used to remove all "non prime" numbers from a list; you can do this by finding a prime number, then checking off all multiples of that prime in your list. The next number "not checked off" is your next prime - you report it (with yield), then continue checking off again. You only need to check for factors less than the square root - factors greater than the square root have a corresponding factor less than the square root, so they have alread been found.

Unfortunately, when it comes to printing out the primes, you can't "stop in the middle". For example, 101 is prime; but if you only loop until 11, you will never discover that it's there. So there need to be two steps:

1) loop over all "possible multiples" - here you can go "only up to the square root"

2) check the list for all numbers that haven't been checked off - here you have to "go all the way"

This makes the following code:

def p(n):
  is_p=[False]*2 + [True]*(n-1)
  for i in range(2, int(n**0.5)):
    if is_p[i]:
        for j in range(i*i, n, i):
            is_p[j] = False
  for i in range(2, n):
    if is_p[i]:
      yield i

print list(p(102))

The result is a list of primes up to and including 101.

Answer 2

Your logic is correct, except for the for loop. It terminates after reaching sqrt(n)-1. For p(100), it will run only from 2 to 9. Hence you get prime numbers only till 9.

Answer 3

Your use of the square root is terminating your results early. If you want to yield all the primes up to 100, your loop has to go to 100.

The square root isn't necessary in your code because it's implied in your second for loop. If i*i < n then i < sqrt(n).