#1
  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))
    Thanks in advance.
    Last edited by pencury; February 12th, 2013 at 11:24 AM. Reason: Formatting
  2. #2
  3. Contributing User
    Devshed Demi-God (4500 - 4999 posts)

    Join Date
    Aug 2011
    Posts
    4,843
    Rep Power
    480
    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!
  4. #3
  5. 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.
  6. #4
  7. Contributing User
    Devshed Demi-God (4500 - 4999 posts)

    Join Date
    Aug 2011
    Posts
    4,843
    Rep Power
    480
    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!

IMN logo majestic logo threadwatch logo seochat tools logo