1

I'm doing a project on Sieve of Atkins and I was exploring why this algorithm was created. From what I understood was that it was a way of finding prime numbers and it ran faster than Sieve of Eratosthenes. But from what I've read, Sieve of Atkins only theoretically runs faster, and this never happens in practice. I tested it out using these two implementations from GeeksForGeeks and Eratosthenes always ran faster. But I also have read conflicting viewpoints like this wiki page which says that Atkins runs faster and can be optimized to theoretically run faster.

Here is the wiki(it discusses this in the complexity section): https://en.wikipedia.org/wiki/Generation_of_primes

Sieve of Atkins implementation: https://www.geeksforgeeks.org/sieve-of-atkin/ Sieve of Eratosthenes implementation: https://www.geeksforgeeks.org/sieve-of-eratosthenes/

Can someone explain which one should be running faster? And why the theoretical time complexity of sieve of atkins can never be acheived.

Ðаn
  • 10,934
  • 11
  • 59
  • 95
CrashMan123
  • 57
  • 6
  • from that geeks-for-geeks link: "a better _theoretical_ _asymptotic_ complexity". Key words to understand are in italics ... - "theoretical" - meaning, on an idealized computer with only certain operations; "asymptotic" - meaning as _n_, the number of primes sieved, goes to infinity ... - welcome to the world of computational complexity as understood in the computer science community ... - to _really_ drive this home look up the recent _n log n_ algorithm for "multiplication of two large numbers" and see where it is expected to improve upon other not-so-optimal algorithms ... – davidbak Apr 05 '21 at 02:01
  • Thanks for the response! Why does theoretical time complexity matter if it isnt something that can be achieved on modern computers? I guess another question is what would it take for the theoretical time complexity to be acheived? – CrashMan123 Apr 05 '21 at 02:27
  • Why do people try to [be the first to free climb ridiculous cliffs](https://en.wikipedia.org/wiki/List_of_first_ascents_(sport_climbing))? Fame and fortune, my friend, fame and fortune. Plus, _sometimes_, other work following up on the insight will lead to a more practical algorithm. – davidbak Apr 05 '21 at 02:32
  • So as you stated earlier, theoretical means "on an idealized computer with only certain operation"... this gives me the impression that this theoretical time complexity can be practical on some sort of super computer. Is that true? – CrashMan123 Apr 05 '21 at 02:34
  • Not really. To give you an example, the "idealized" computer generally has no caching to speed up memory operations (all memory operations are the same unit time), no pipelining to speed up arithmetic operations (all arithmetic operations take the same unit time), etc. etc. etc. Even ordinary computers have these advantages now: but the _idealized_ computer - which has it the properties it has so the algorithms can be _analyzed at all_ (and then compared to each other) - is so much simpler. – davidbak Apr 05 '21 at 02:36
  • It's necessary to use a (simple) idealized computer to analyze algorithms for the same reason other theoreticians joke about ["a spherical cow in vacuum"](https://en.wikipedia.org/wiki/Spherical_cow). – davidbak Apr 05 '21 at 02:39
  • 1
    I haven't even mentioned that complexity analysis of algorithms _ignores constant factors_. I won't explain that here, you can easily find lots of articles/blog posts/books that will explain that too. – davidbak Apr 05 '21 at 02:43
  • there are only 25 questions on this tag. you should be able to go through them; look for the answers/comments by the user GordonBGood where he states the reasons for it, mainly that SoE is extendable to higher wheel factorizations whereas SoA - not. – Will Ness Nov 18 '22 at 23:37
  • e.g. [here](https://stackoverflow.com/a/20559687/849891). but an academic [paper](https://www.cambridge.org/core/journals/lms-journal-of-computation-and-mathematics/article/two-compact-incremental-prime-sieves/8C93ED669EABD7C3074BD44BC487747F) mentioned [here](https://stackoverflow.com/a/74483926/849891) claims its incremental formulation of SoA sublinear, so it must at some point become faster than SoE, if the article is correct. but perhaps its assumptions include infinite memory accessible at equal speeds everywhere. – Will Ness Nov 19 '22 at 11:01

0 Answers0