Reputation: 57
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