Sunday, July 15, 2007

Sieve of Eratosthenes, Python, Set Operations

{

I pretty much broke down after TechEd. I thought I'd be patient enough to wait for Ruby but because Python is most mature I have started to learn it, whitespaces or no.

The first thing I did was check out Guido van Rossum's tutorial for programmers, which was an excellent first step. I've followed that up with some random programming - a lot of fun so far.

I was wondering about the set operations in python and how that made a difference in programming since there aren't syntactical equivalents in .NET. Incidentally at the time I was reading The Man Who Loved Only Numbers and ran across a short description of the Sieve of Eratosthenes as a way of finding primes. I thought it would be a good way to check out the set operations of Python.

I wrote the following:


from System import *

def multiples(num, thresh):
multi = []
for i in range(2,thresh):
m = num * i
if(m < thresh):
multi.append(m)
else:
break
return multi

primeThresh = 5000
print DateTime.Now.ToString("MM/dd/yyyy hh:mm:ss")
nums = range(2,primeThresh)

for n in nums:
nums = set(nums) - set(multiples(n, primeThresh))

print nums

print DateTime.Now.ToString("MM/dd/yyyy hh:mm:ss")


Interesting, but slow. The way I may do something like that in C# (which also works just fine in Python) would be this, which I wrote later:


from System import *

primeThresh = 5000
print DateTime.Now.ToString("MM/dd/yyyy hh:mm:ss")
nums = range(2,primeThresh)

for n in nums:
for m in range(2,primeThresh):
try:
mult = n * m
if(mult > primeThresh):
break
nums.remove(mult)
except:
pass

print nums

print DateTime.Now.ToString("MM/dd/yyyy hh:mm:ss")


It's a lot faster than the previous approach which makes sense - doing set algebra on large sets should take a long time... but that begs the question: are those set operations dangerous (ie. so slow as to be costly).

I'm wondering what's "pythonic" and how a jedi would write this most effeciently.

}

1 comment:

marc.gaudette said...

I also found The Man Who Loved Only Numbers a fun read. Since you're interested in the sieve, site www.primestructure.com has an extensive discussion re. adding structure to it.

Marc