"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
.