http://burntjet.co.uk/maths/primes/sieves.php#eq_sieve_div
I have read that Sieve of Eratosthenes algorithm can be speeded up with wheel factorization. Can similar be done with Euler's sieve (while in between taking out composite numbers from the list of N numbers)?
Because for number 2 every second number is removed (list reduced). Then after that; for multiplications of 3, it is every third number removed starting from number 3. For number 5 we have composite numbers of 5 in a sequence +7th,+3th number… removed starting from number 5. For number 7 it is a +12th,+7th,+4th,+7th,+4th,+7th,+12th,+3th…and again… starting from number 7 in the list…
And so on….?
Was this implemented before?
Maybe next paper (Fabio’s sieve
) can be of help?
http://arxiv.org/find/all/1/all:+AND+fabio+sieve/0/1/0/all/0/1
Best Answer
Your link doesn't seem reliable. In particular, it seems to suggest that one actually multiplies numbers to see which point to cross out next. That would be a terrible implementation -- one of the most computationally important features of a sieve is that you don't have to do any expensive arithmetic to iterate over the points to cross out: you just do addition.
I've not heard of Euler's sieve before. Judging from Wikipedia's description, it is a technique for proving things, not a technique for computing things.
While there may be ways to avoid the multiplications, I don't think the underlying idea is salvageable as a computational technique. How do you determine which numbers to 'multiply' by? I'm having difficulty imagining any technique that has a chance of competing with the usual method if just stepping through the table crossing out points without caring whether or not they are already crossed out.
One of the main problems is that there is very little to gain. Composite numbers simply don't cluster together enough for there to be much benefit of making a complicated algorithm to avoid double marking points... and most of what benefit exists has already been given to you by the wheel sieve.