Sieve of Atkin explanation

primes sieve-of-eratosthenes sieve-of-atkin
marc lincoln picture marc lincoln · Jun 21, 2009 · Viewed 20.4k times · Source

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

Noldorin picture Noldorin · Jun 21, 2009

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:

Hope that helps.

Related questions

Program to find prime numbers

I want to find the prime number between 0 and a long variable but I am not able to get any output. The program is using System; using System.Collections.Generic; using System.Linq; using System.Text; namespace ConsoleApplication16 { class Program { …

Read More
Sieve of Eratosthenes - Finding Primes Python

Just to clarify, this is not a homework problem :) I wanted to find primes for a math application I am building & came across Sieve of Eratosthenes approach. I have written an implementation of it in Python. But it's terribly …

Read More
Finding prime numbers with the Sieve of Eratosthenes (Originally: Is there a better way to prepare this array?)

Note: Version 2, below, uses the Sieve of Eratosthenes. There are several answers that helped with what I originally asked. I have chosen the Sieve of Eratosthenes method, implemented it, and changed the question title and tags appropriately. Thanks to everyone …

Read More