Sieve of Eratosthenes: Difference between revisions

The above examplecan hasbe beenimproved leftin to show its problemsefficiency, as follows:

1. The generation of the wheel works just to generate a small wheel list 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 dueneeds to it using essentially a trial division to determine the wheel (Greatest Common Divisor - gcd - works by repeated division). A programmatic wheelbe generatordone based on sieve culling which is much better as to performance and can be used without inserting the generated table.

2. TheImproving above routine uses ridiculousthe means to re-generate the position on the wheel for the recursive base primes inwithout 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.

Note that the "wheelGen" code could be used to not need to do further culling at all by continuously generating wheels until the square of the "firstSievePrime|" is greater than the range as there are no composites left up to that limit, but this is always slower than a SoE due to the high overhead in generating the wheels - this would take a wheel generation of 1229 (number of primes to the square root of a hundred thousand is ten thousand) to create the required wheel sieved to a hundred million; however, the theoretical (if the time to advance through the lists per element were zero, which of course it is not) asymptotic performance would be O(n) instead of O(n log (log n)) where n is the range sieved. Just another case where theory supports (slightly) reduced number of operations, but practicality means that the overheads to do this are so big as to make it useless for any reasonable range ;-) !