### Thread: Sieve of Eratosthenes

1. No Profile Picture
Registered User
Devshed Newbie (0 - 499 posts)

Join Date
Feb 2013
Posts
2
Rep Power
0

#### 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))```
Last edited by pencury; February 12th, 2013 at 11:24 AM. Reason: Formatting
2. 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.
3. No Profile Picture
Registered User
Devshed Newbie (0 - 499 posts)

Join Date
Feb 2013
Posts
2
Rep Power
0
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.
4. In sieve add 1 to the high end of the range
1 + int(math.sqrt(n))