February 11th, 2013, 10:44 PM

Sieve of Eratosthenes
I'm having trouble with an implementation of the Sieve of Eratosthenes that I wrote in Python recently. Certain values, such as the one printed in the example, are off by one. I can't seem to find the error however.
Code:
import math
def list_rm(l, v):
return [val for val in l if val != v]
def sieve(n):
l = []
for i in range(2, n):
l.append(i)
for i in range(2, int(math.sqrt(n))):
if l[i  2] != 1:
for j in range(i ** 2, n, i):
l[j  2] = 1
return len(list_rm(l, 1))
def is_prime(n):
for i in range(2, n):
if n % i == 0:
return False
return True
def p(n):
count = 0
for i in range(2, n):
if is_prime(i):
count += 1
return count
print(sieve(1000))
Thanks in advance.
Last edited by pencury; February 12th, 2013 at 12:24 PM.
Reason: Formatting
February 12th, 2013, 12:13 PM

Please read your post. Would you answer a question with a python program stretched out on a 467 character line with multiple blocks? And read link at my post to learn about whitespace preservation.
[code]
Code tags[/code] are essential for python code and Makefiles!
February 12th, 2013, 12:25 PM

Originally Posted by b49P23TIvg
Please read your post. Would you answer a question with a python program stretched out on a 467 character line with multiple blocks? And read link at my post to learn about whitespace preservation.
Sorry I forgot preview it, I hope it's better now.
February 12th, 2013, 12:55 PM

In sieve add 1 to the high end of the range
1 + int(math.sqrt(n))
[code]
Code tags[/code] are essential for python code and Makefiles!