Ruby and Python (was Re: Why is Python a good first scripting language?)

[Magnus Lyckå]

Michael Hudson wrote:
> It seems to be three-and-a-bit times quicker than yours (and it may be
> algorithmically better too, not sure).  The *fastest* I know is due to
> Christian Tismer, and is completely out of control:
> 
> def tissieve6(n):
>     if n < 2: return []
>     candidates = range(-1, n+1, 3)
>     # yes they are wrong, adjusted later.
>     sq = math.sqrt(n)
>     end = sys.maxint
>     candidates[:2] = [0, 0]
>     for p in candidates:
>         if p:
>             if p%2==0: p=p-1
>             if p>sq : break
>             dist = p2 = p+p
>             if p%3 == 1: dist=dist+dist
>             dist = dist/3
>             try: # indexing too far
>               for q in xrange( (p*p+3)/3, end, p2):\
>                 candidates[q] = 0 ;\
>                 candidates[q+dist] = 0
>             except:pass
>     candidates[:2] = [2, 3]
>     candidates = filter(None, candidates)
>     for i in xrange(1, len(candidates)):
>         if candidates[i]%2 == 0:\
>             candidates[i] = candidates[i]-1
>     return candidates

I tried this, with surprising result... (Python 2.2.1)
The surprise isn't the speed, but that Tismer's version
finds more primes, like 25, 35, and 49... Something missing?

Alex Martelli Version
0.000488050855626
2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 
71, 73,
79, 83, 89, 97
Tim Peters Version
0.000227682568595
[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 
71, 73,
  79, 83, 89, 97]
Christian Tismer Version
0.000374907984115
[2, 3, 5, 7, 11, 13, 17, 19, 23, 25, 29, 31, 35, 37, 41, 43, 47, 49, 53, 
55, 59,
  61, 65, 67, 71, 73, 77, 79, 83, 85, 89, 91, 95, 97]