mrpeenut24
November 3rd, 2007, 07:09 PM
I'm trying to implement the Sieve of Eratosthenes (http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes) in python. (I've seen that it's already been implemented using yield, however, I'd like to try it with simple lists.) And here's what I have so far:
#!/usr/bin/python
from math import sqrt
#initialize an empty list that will store every number up to
#limit at first then delete the numbers that aren't prime
primes = []
#generate primes up to this number
limit = 30
#append all numbers up to limit into primes
##there has to be a faster way...
for i in xrange(2,limit+1):
primes.append(i)
#reset i to use later
i = 0
#start at beginning of primes := 2
## so long as this entry in primes is less than the square
## root of limit, check if it's divisible by anything else in the list
## i believe the problem lies in not resetting i?
while primes[i] < sqrt(limit):
for j in xrange(i, len(primes)):
if not primes[j] == primes[i]:
if primes[j] % primes[i] == 0:
## print out i & primes[i] and j & primes[j]
print "[",i,"]",primes[i]," xx [",j,"]",primes[j]
# j is divisible by i, remove it
## with this line not in place, everything prints out correctly above
## however, with it here, it messes up, keeping i and primes[j] == 0
#primes.remove(j)
i = i + 1
You may have to run the script to see what it does, but I'm not sure what the problem is. Without that primes.remove(j) line, everything works fine, however, when I add it, it messes everything up. I'm assuming it shrinks the list, which I'm counting on happening, but I think that's what's causing the problem. Anyone see what I'm missing?
#!/usr/bin/python
from math import sqrt
#initialize an empty list that will store every number up to
#limit at first then delete the numbers that aren't prime
primes = []
#generate primes up to this number
limit = 30
#append all numbers up to limit into primes
##there has to be a faster way...
for i in xrange(2,limit+1):
primes.append(i)
#reset i to use later
i = 0
#start at beginning of primes := 2
## so long as this entry in primes is less than the square
## root of limit, check if it's divisible by anything else in the list
## i believe the problem lies in not resetting i?
while primes[i] < sqrt(limit):
for j in xrange(i, len(primes)):
if not primes[j] == primes[i]:
if primes[j] % primes[i] == 0:
## print out i & primes[i] and j & primes[j]
print "[",i,"]",primes[i]," xx [",j,"]",primes[j]
# j is divisible by i, remove it
## with this line not in place, everything prints out correctly above
## however, with it here, it messes up, keeping i and primes[j] == 0
#primes.remove(j)
i = i + 1
You may have to run the script to see what it does, but I'm not sure what the problem is. Without that primes.remove(j) line, everything works fine, however, when I add it, it messes everything up. I'm assuming it shrinks the list, which I'm counting on happening, but I think that's what's causing the problem. Anyone see what I'm missing?