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


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.

  • 1
    $\begingroup$ How do you determine which numbers to 'multiply' by? Well you always multipla by remaining numbers. But if there is no formula for finding patterns for jumps to the next composite(instead of multiplication) for certain prime numbers than you first test those jumps until they repeat itself. Yes there are difficulties because patterns are growing large quite fast. For number 7 there are 8 distinct jumps. But i thought this would be still better than real multiplication. $\endgroup$ Apr 29 '12 at 23:13
  • 1
    $\begingroup$ @Bojan: I assert a straightforward implementation of finding the remaining numbers would take just as long as sieving the normal way -- and so you slow yourself down by by doing so. While I can imagine some tricks that might speed up the search, I believe it unlikely you can get a net benefit out of it. $\endgroup$
    – user14972
    Apr 30 '12 at 2:11
  • $\begingroup$ To restate my expectation -- a wheel sieve is giving you the same benefit that Euler's method would give you. At some point, it becomes inefficient to continue to bigger wheels... and my expectation is that Euler's trick would be even less efficient for computation. $\endgroup$
    – user14972
    Apr 30 '12 at 2:24
  • $\begingroup$ An Euler's sieve example is at brand.site.co.il/riddles/201701a.html. This is shown to be $O(n)$. For an even better algorithm, see brand.site.co.il/riddles/201702a.html $\endgroup$ Feb 22 '19 at 21:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.