[Tutor] primes (generator)

[Karl Pflästerer]

On 19 Mrz 2005, glingl at aon.at wrote:

[Code]
> Maybe sombody likes to compare these algorithms to the
> ones mentioned before in this thread. I would be
> interested in the results.

I did it and on my machine here (a slow one) the following straight
forward version is the fastest one.

It's no iterator and since all the numbers are stored in a list you need
place proportional the number of entries but it's fast and it works
nearly the same way the original sieve of Erasthosthens algorithm works.

Here it is no error to modify the list which gets iterated over.

def sieve (max):
    max = max + 1
    border = round(max**0.5)
    nums = range(0, max)
    nums[0] = nums[1] = None
    for p in nums:
        if p:
            if p >= border: break 
            for i in xrange(p+p, max, p):
                nums[i] = None
    return filter(None, nums)



   Karl
-- 
Please do *not* send copies of replies to me.
I read the list