primes - Sieve of Atkin explanation

Question

I am doing a project at the moment and I need an efficient method for calculating prime numbers. I have used the sieve of Eratosthenes but, I have been searching around and have found that the sieve of Atkin is a more efficient method. I have found it difficult to find an explanation (that I have been able to understand!) of this method. How does it work? Example code (preferably in C or python) would be brilliant.

Edit: thanks for your help, the only thing that I still do not understand is what the x and y variables are referring to in the pseudo code. Could someone please shed some light on this for me?

Answer 1

The wiki page is always a good place to start, since it explains the algorithm in full and provides commented pseudocode. (N.B. There's a lot of detail, and since the wiki website is reliably up, I won't quote it here.)

For references in the specific languages you mentioned:

• C implementation (optimised)
• Python implementation

Hope that helps.