From Wikipedia (2010-02-24):
In mathematics, the sieve of Atkin is a fast, modern algorithm for finding all
prime numbers up to a specified integer. It is an optimized version of the ancient
sieve of Eratosthenes,
but does some preliminary work and then marks off multiples of primes squared,
rather than multiples of primes.
It was created by
A. O. L. Atkin and
Daniel J. Bernstein.
This is my translation of the
pseudocode to f#:
// Generates a list of all primes below limit
let sieveOfAtkin limit =
// initialize the sieve
let sieve = Array.create (limit + 1) false
// put in candidate primes:
// integers which have an odd number of
// representations by certain quadratic forms
let inline invCand n pred =
if n < limit && pred then sieve.[n] <- not sieve.[n]
let sqrtLimit = int (sqrt (float limit))
for x = 1 to sqrtLimit do
for y = 1 to sqrtLimit do
let xPow2 = x * x
let yPow2 = y * y
let n = 4 * xPow2 + yPow2 in invCand n (let m = n % 12 in m = 1 || m = 5)
let n = 3 * xPow2 + yPow2 in invCand n (n % 12 = 7)
let n = 3 * xPow2 - yPow2 in invCand n (x > y && n % 12 = 11)
// eliminate composites by sieving
let rec eliminate n =
if n <= sqrtLimit
then if sieve.[n]
then let nPow2 = n * n
for k in nPow2 .. nPow2 .. limit do
Array.set sieve k false
eliminate (n + 2)
eliminate 5
// Generate list from the sieve (backwards)
let rec generateList acc n =
if n >= 5 then generateList (if sieve.[n] then n :: acc else acc) (n - 1)
else acc
2 :: 3 :: (generateList [] limit)
On my MacBook Pro 2.66 GHz Intel Core 2 Duo it generates all primes
below 10.000.000 in 557 milliseconds:
> #time;;
--> Timing now on
> sieveOfAtkin 10000000;;
Real: 00:00:00.557, CPU: 00:00:00.471, GC gen0: 0
val it : int list =
[2; 3; 5; 7; 11; 13; 17; 19; 23; 29; 31; 37; 41; 43; 47; 53; 59; 61; 67; 71;
73; 79; 83; 89; 97; 101; 103; 107; 109; 113; 127; 131; 137; 139; 149; 151;
157; 163; 167; 173; 179; 181; 191; 193; 197; 199; 211; 223; 227; 229; 233;
239; 241; 251; 257; 263; 269; 271; 277; 281; 283; 293; 307; 311; 313; 317;
331; 337; 347; 349; 353; 359; 367; 373; 379; 383; 389; 397; 401; 409; 419;
421; 431; 433; 439; 443; 449; 457; 461; 463; 467; 479; 487; 491; 499; 503;
509; 521; 523; 541; ...]