CrashMan123
CrashMan123

Reputation: 57

If the time complexity of Sieve of Atkins is better than Sieve of Eratosthenes, why does Eratosthenes always have a quicker runtime

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.

Upvotes: 1

Views: 255

Answers (0)

Related Questions