Sieve of Eratosthenes: Difference between revisions

1. The generation of the wheel works just to generate a small wheel list of primes which has been directly inserted into the code as here, but is very inefficient for generation of large wheels such as the 2/3/5/7/11/13/17 wheel, which has 92160 cyclic elements; this is due to it using essentially a trial division to determine the wheel (Greatest Common Divisor - gcd - works by repeated division). A programmatic wheel generator based on sieve culling is much better as to performance and can be used without inserting the generated table.

2. The above routine uses ridiculous means to re-generatedgenerate the position on the wheel for the recursive base primes in the use of `dropWhile`, etc. The below improved code uses a copy of the place in the wheel for each found base prime for ease of use in generating the composite number to-be-culled chains.

union xs@(x:xs') ys@(y:ys') =

if| x < y then= x : union xs' ys else

if| y < x then= y : union xs ys' else

| otherwise = x : union xs' ys' -- x and y must be equal!</lang>

TheWhen compiled with -O2 optimization and -fllvm (the LLVM back end), the above code is over twice as fast as the Odds-Only version andas it should be as that is probablyabout the fastestratio purelyof functionalreduced incrementaloperations sieveminus heresome slightly increased operation complexity, sieving the primes to a 100hundred million in about tenseven seconds on a modern middle range desktop computer. It is almost twice as fast as the "primesW" version due to the increased algorithmic efficiency!