20 Dec
2000
20 Dec
'00
2:12 p.m.
There are numerous ways of optimising sieving for primes, none of which have much to do with this list. For example, two suggestions: (1) for each k modulo 2*3*5*7, if k is divisible by 2/3/5 or 7, ignore, otherwise sieve separately for this k on higher primes. (Or you might use products of more or less primes, depending on memory and how high you were going.) (2) use bitwise arithmetic. If you look in the literature I think you'll find plenty more possibilities. I don't really see why any of this has anything to do with Haskell though. When it comes to seriously icky bit-twiddling algorithms I don't think Haskell has much to offer over C, especially as you'd have to make everything unboxed if you want comparable speed.