Programming Pauls of Wisdom

Erastothenes

Not too sure about this one. I am interested in seeing if a code example I struggle to understand could be made clearer using a different approach.

I looked at http://gflanagan.net/site/python/sci/sieve_of_eratosthenes.html
and it was not clear what was going on

It was curiously difficult

import string

top = 50
listA = [[x] for x in range(0,top+1)]
listA[0] = [] #blank out 1
listA[1] = [] #blank out 1
listB = []

def getfirstvisiblenumber(prime):
"""given [[], [3], [], [5], [], [7], rtn first visible number > prime
"""
for elem in listA:
if len(elem) > 0:
number = elem[0]
if number > prime:
return number

def remainingnumbers(prime):

ptr = prime**2

while 1: #stop if exceed upperbound - this is valid as always list is in order
if ptr >= len(listA): break
listA[ptr] = [] # "remove" the value is [[2],[3] .. becomes [[],[3]...
ptr += prime # move forwad the prime number in the list, but as we just removed a val drop one
if ptr >= len(listA): break
return listA[0]

def printlistA():

st = 0
for i in listA:
if st % 10:
print string.center(str(i),5),
st += 1
else:
print string.center(str(i),5)
st += 1



if __name__ == '__main__':

nextprime = 2
printlistA()
while nextprime is not None:
listB.append(nextprime)
remainingnumbers(nextprime)
print
print nextprime
printlistA()
nextprime = getfirstvisiblenumber(nextprime)



print listB[:-1]
print listA


However the thngs to note were the original used division to see if it was not a prime. Which seems to defeat the sieve idea.

Anyway...

posted by paul @ 6:07 PM