Sieve Of Atkin

February 12, 2010

We examined the use of the Sieve of Eratosthenes for enumerating the prime numbers, a method that dates to the ancient Greeks, in two previous exercises. Just a few years ago, in 2004, A. O. L. Atkin and D. J. Bernstein developed a new method, called the Sieve of Atkin, that performs the same task more quickly. The new method first marks squarefree potential primes, then eliminates those potential primes that are not squarefree.

Atkin’s sieve begins with a boolean array (bits are fine) of length n equal to the number of items to be sieved; each element of the array is initially false.

Squarefree potential primes are marked like this: For each element k of the array for which k ≡ 1 (mod 12) or k ≡ 5 (mod 12) and there exists some 4x² + y² = k for positive integers x and y, flip the sieve element (set true elements to false, and false elements to true). For each element k of the array for which k ≡ 7 (mod 12) and there exists some 3x² + y² = k for positive integers x and y, flip the sieve element. For each element k of the array for which k ≡ 11 (mod 12) and there exists some 3x² – y² = k for positive integers x and y with x > y, flip the sieve element.

Once this preprocessing is complete, the actual sieving is performed by running through the sieve starting at 7. For each true element of the array, mark all multiples of the square of the element as false (regardless of their current setting). The remaining true elements are prime.

Your task is to write a function to sieve primes using the Sieve of Atkin. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

About these ads

Pages: 1 2

6 Responses to “Sieve Of Atkin”

  1. Jon said

    The equations that are like: x² + y² = n
    should be: x² + y² = k

  2. programmingpraxis said

    Thanks. Fixed.

  3. Paul Hofstra said

    According to the Wikipedia page the equation x^2 + y^2 = k should read 4*x^2 + y^2 = k. Your code is also using the factor 4.

  4. programmingpraxis said

    Fixed again. Thanks.

  5. Mike said

    Tightened up the loop limits a little bit. It’s about 50% slower than a plain sieve on getting the primes less than a million (0.96 sec vs. 0.63 sec).

    from math import sqrt
    
    limit = 1000000
    
    def atkins(limit=1000000):
        '''use sieve of atkins to find primes <= limit.'''
        primes = [False] * limit
        sqrt_limit = int( sqrt( limit ) )
    
        x_limit = int( sqrt( ( limit + 1 ) / 2 ) )
        for x in xrange( 1, x_limit ):
            xx = x*x
    
            for y in xrange( 1, sqrt_limit ):
                yy = y*y
    
                n = 3*xx + yy
                if n <= limit and n%12 == 7:
                    primes[n] = not primes[n]
                    
                n += xx
                if n <= limit and n%12 in (1,5):
                    primes[n] = not primes[n]
                    
                if x > y:
                    n -= xx + 2*yy
                    if n <= limit and n%12 == 11:
                        primes[n] = not primes[n]
    
        for n in xrange(5,limit):
            if primes[n]:
                for k in range(n*n, limit, n*n):
                    primes[k] = False
    
        return [2,3] + filter(primes.__getitem__, xrange(5, limit))
    
  6. ivan said

    escucho maravillas de la criba de atkin pero todavia no he visto un codigo que me funcione yo hice otro tipo de criba qe trabaja diferebte y quiero comparar yo saco hasta 600 millones la saco en 14 seg en visual c pero no se si esta criba es mejor o peor, trabajo con una lenovo n200

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Follow

Get every new post delivered to your Inbox.

Join 600 other followers

%d bloggers like this: