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 Wikipedia page looks pretty comprehensive - it even has links to implementations in C and Python.

Answer 2

The wiki page is always a good place to start. If you see the end of the page, it links to examples in both C and Python:

• http://cr.yp.to/primegen.html
• http://krenzel.info/?p=83

Here's the Python function, copied from the second link:

def sieveOfErat(end):  
  if end < 2: return []  

  #The array doesn't need to include even numbers  
  lng = ((end/2)-1+end%2)  

  # Create array and assume all numbers in array are prime  
  sieve = [True]*(lng+1)  

  # In the following code, you're going to see some funky  
  # bit shifting and stuff, this is just transforming i and j  
  # so that they represent the proper elements in the array.  
  # The transforming is not optimal, and the number of  
  # operations involved can be reduced.  

  # Only go up to square root of the end  
  for i in range(int(sqrt(end)) >> 1):  

    # Skip numbers that aren’t marked as prime  
    if not sieve[i]: continue  

    # Unmark all multiples of i, starting at i**2  
    for j in range( (i*(i + 3) << 1) + 3, lng, (i << 1) + 3):  
      sieve[j] = False  

  # Don't forget 2!  
  primes = [2]  

  # Gather all the primes into a list, leaving out the composite numbers  
  primes.extend([(i << 1) + 3 for i in range(lng) if sieve[i]])  

  return primes

Answer 3

He creado mi propia Criba que no necesita cuadrados, por tanto no es parecida a la de erastotenes, pero con muchas diferencias, por tanto me permite sacar del 1 al 600 millones cuales son primos en 14 segundos, en una laptop n200 en lenguaje c y en php un lenguaje lento, 100 millones estoy buscando a que sociedad de matematica se le presentan resultados. Estoy a punto de cambiar el programa para que funcione en redes al cambiar la forma de almacenar los datos. Ivan Mrsnik

Translation (courtesy of Google Translate)

I created my own sieve need not square, so there is similar to that of Eratosthenes, but with many differences, so I can get 1 to 600 million of whom are cousins in 14 seconds in a laptop n200 c language in php slow language, 100 million'm looking to society mathematical results are presented. I'm about to change the program to run on networks by changing the way of storing data. Ivan Mrsnik