# Sieve of Atkin

Given a limit, print all primes smaller than or equal to the given limit.

Examples :

```Input:  limit = 10
Output: 2, 3, 5, 7

Input:  limit = 20
Output: 2, 3, 5, 7, 11, 13, 17, 19 ```

We have discussed below algorithms for the above task.
Sieve of Eratosthenes
Sieve of Sundaram

The sieve of Atkin is a modern algorithm for finding all prime numbers up to a specified integer. Compared with the ancient Sieve of Eratosthenes , which marks off multiples of primes, it does some preliminary work and then marks off multiples of squares of primes, that’s why it has a better theoretical asymptotic complexity with Complexity of (N / (log log N))

The algorithm:

1. Create a results list, filled with 2, 3, and 5.
2. Create a sieve list with an entry for each positive integer; all entries of this list should initially be marked non prime.
3. For each entry number n in the sieve list, with modulo-sixty remainder r:
1. If r is 1, 13, 17, 29, 37, 41, 49, or 53, flip the entry for each possible solution to 4x2 + y2 = n.
2. If r is 7, 19, 31, or 43, flip the entry for each possible solution to 3x2 + y2 = n.
3. If r is 11, 23, 47, or 59, flip the entry for each possible solution to 3x2 – y2 = n when x > y.
4. If r is something else, ignore it completely..
5. Take the next number in the sieve list still marked prime.
6. Include the number in the results list.
7. Square the number and mark all multiples of that square as non prime. Note that the multiples that can be factored by 2, 3, or 5 need not be marked, as these will be ignored in the final enumeration of primes.
8. Repeat steps four through seven.

Below is the implementation of above algorithm.

## C++

 `// C++ program for implementation of Sieve of Atkin ` `#include ` `using` `namespace` `std; ` ` `  `int` `SieveOfAtkin(``int` `limit) ` `{ ` `    ``// 2 and 3 are known to be prime ` `    ``if` `(limit > 2) ` `        ``cout << 2 << ``" "``; ` `    ``if` `(limit > 3) ` `        ``cout << 3 << ``" "``; ` ` `  `    ``// Initialise the sieve array with false values ` `    ``bool` `sieve[limit]; ` `    ``for` `(``int` `i = 0; i < limit; i++) ` `        ``sieve[i] = ``false``; ` ` `  `    ``/* Mark siev[n] is true if one  ` `       ``of the following is true: ` `    ``a) n = (4*x*x)+(y*y) has odd number of  ` `       ``solutions, i.e., there exist ` `       ``odd number of distinct pairs (x, y)  ` `       ``that satisfy the equation and ` `        ``n % 12 = 1 or n % 12 = 5. ` `    ``b) n = (3*x*x)+(y*y) has odd number of  ` `       ``solutions and n % 12 = 7 ` `    ``c) n = (3*x*x)-(y*y) has odd number of  ` `       ``solutions, x > y and n % 12 = 11 */` `    ``for` `(``int` `x = 1; x * x < limit; x++) { ` `        ``for` `(``int` `y = 1; y * y < limit; y++) { ` `             `  `            ``// Main part of Sieve of Atkin ` `            ``int` `n = (4 * x * x) + (y * y); ` `            ``if` `(n <= limit && (n % 12 == 1 || n % 12 == 5)) ` `                ``sieve[n] ^= ``true``; ` ` `  `            ``n = (3 * x * x) + (y * y); ` `            ``if` `(n <= limit && n % 12 == 7) ` `                ``sieve[n] ^= ``true``; ` ` `  `            ``n = (3 * x * x) - (y * y); ` `            ``if` `(x > y && n <= limit && n % 12 == 11) ` `                ``sieve[n] ^= ``true``; ` `        ``} ` `    ``} ` ` `  `    ``// Mark all multiples of squares as non-prime ` `    ``for` `(``int` `r = 5; r * r < limit; r++) { ` `        ``if` `(sieve[r]) { ` `            ``for` `(``int` `i = r * r; i < limit; i += r * r) ` `                ``sieve[i] = ``false``; ` `        ``} ` `    ``} ` ` `  `    ``// Print primes using sieve[] ` `    ``for` `(``int` `a = 5; a < limit; a++) ` `        ``if` `(sieve[a]) ` `            ``cout << a << ``" "``; ` `} ` ` `  `// Driver program ` `int` `main(``void``) ` `{ ` `    ``int` `limit = 20; ` `    ``SieveOfAtkin(limit); ` `    ``return` `0; ` `} `

## Java

 `// Java program for implementation of Sieve ` `// of Atkin ` `class` `GFG { ` ` `  `    ``static` `int` `SieveOfAtkin(``int` `limit) ` `    ``{ ` `        ``// 2 and 3 are known to be prime ` `        ``if` `(limit > ``2``) ` `            ``System.out.print(``2` `+ ``" "``); ` ` `  `        ``if` `(limit > ``3``) ` `            ``System.out.print(``3` `+ ``" "``); ` ` `  `        ``// Initialise the sieve array with ` `        ``// false values ` `        ``boolean` `sieve[] = ``new` `boolean``[limit]; ` ` `  `        ``for` `(``int` `i = ``0``; i < limit; i++) ` `            ``sieve[i] = ``false``; ` ` `  `        ``/* Mark siev[n] is true if one of the ` `        ``following is true: ` `        ``a) n = (4*x*x)+(y*y) has odd number  ` `           ``of solutions, i.e., there exist  ` `           ``odd number of distinct pairs  ` `           ``(x, y) that satisfy the equation  ` `           ``and    n % 12 = 1 or n % 12 = 5. ` `        ``b) n = (3*x*x)+(y*y) has odd number  ` `           ``of solutions and n % 12 = 7 ` `        ``c) n = (3*x*x)-(y*y) has odd number  ` `           ``of solutions, x > y and n % 12 = 11 */` `        ``for` `(``int` `x = ``1``; x * x < limit; x++) { ` `            ``for` `(``int` `y = ``1``; y * y < limit; y++) { ` ` `  `                ``// Main part of Sieve of Atkin ` `                ``int` `n = (``4` `* x * x) + (y * y); ` `                ``if` `(n <= limit && (n % ``12` `== ``1` `|| n % ``12` `== ``5``)) ` ` `  `                    ``sieve[n] ^= ``true``; ` ` `  `                ``n = (``3` `* x * x) + (y * y); ` `                ``if` `(n <= limit && n % ``12` `== ``7``) ` `                    ``sieve[n] ^= ``true``; ` ` `  `                ``n = (``3` `* x * x) - (y * y); ` `                ``if` `(x > y && n <= limit && n % ``12` `== ``11``) ` `                    ``sieve[n] ^= ``true``; ` `            ``} ` `        ``} ` ` `  `        ``// Mark all multiples of squares as ` `        ``// non-prime ` `        ``for` `(``int` `r = ``5``; r * r < limit; r++) { ` `            ``if` `(sieve[r]) { ` `                ``for` `(``int` `i = r * r; i < limit; ` `                     ``i += r * r) ` `                    ``sieve[i] = ``false``; ` `            ``} ` `        ``} ` ` `  `        ``// Print primes using sieve[] ` `        ``for` `(``int` `a = ``5``; a < limit; a++) ` `            ``if` `(sieve[a]) ` `                ``System.out.print(a + ``" "``); ` `        ``return` `0``; ` `    ``} ` ` `  `    ``// Driver code ` `    ``public` `static` `void` `main(String[] args) ` `    ``{ ` `        ``int` `limit = ``20``; ` `        ``SieveOfAtkin(limit); ` `    ``} ` `} ` ` `  `// This code is contributed by Anant Agarwal. `

## Python 3

 `# Python 3 program for  ` `# implementation of  ` `# Sieve of Atkin ` ` `  `def` `SieveOfAtkin(limit): ` ` `  `    ``# 2 and 3 are known ` `    ``# to be prime ` `    ``if` `(limit > ``2``): ` `        ``print``(``2` `, end ``=` `" "``) ` `    ``if` `(limit > ``3``): ` `        ``print``(``3` `, end ``=` `" "``) ` ` `  `    ``# Initialise the sieve  ` `    ``# array with False values ` `    ``sieve ``=` `[``False``] ``*` `limit ` `    ``for` `i ``in` `range``( ``0` `, limit ): ` `        ``sieve[i] ``=` `False` `         `  `    ``'''Mark siev[n] is True if  ` `    ``one of the following is True: ` `    ``a) n = (4*x*x)+(y*y) has odd  ` `    ``number of solutions, i.e.,  ` `    ``there exist odd number of  ` `    ``distinct pairs (x, y) that ` `    ``satisfy the equation and ` `    ``n % 12 = 1 or n % 12 = 5. ` `    ``b) n = (3*x*x)+(y*y) has  ` `    ``odd number of solutions  ` `    ``and n % 12 = 7 ` `    ``c) n = (3*x*x)-(y*y) has  ` `    ``odd number of solutions,  ` `    ``x > y and n % 12 = 11 '''` `    ``x ``=` `1` `    ``while``(x ``*` `x < limit ) : ` `        ``y ``=` `1` `        ``while``(y ``*` `y < limit ) : ` `             `  `            ``# Main part of  ` `            ``# Sieve of Atkin ` `            ``n ``=` `(``4` `*` `x ``*` `x) ``+` `(y ``*` `y) ` `            ``if` `(n <``=` `limit ``and` `(n ``%` `12` `=``=` `1` `or`  `                                ``n ``%` `12` `=``=` `5``)): ` `                ``sieve[n] ^``=` `True` ` `  `            ``n ``=` `(``3` `*` `x ``*` `x) ``+` `(y ``*` `y) ` `            ``if` `(n <``=` `limit ``and` `n ``%` `12` `=``=` `7``): ` `                ``sieve[n] ^``=` `True` ` `  `            ``n ``=` `(``3` `*` `x ``*` `x) ``-` `(y ``*` `y) ` `            ``if` `(x > y ``and` `n <``=` `limit ``and`  `                          ``n ``%` `12` `=``=` `11``): ` `                ``sieve[n] ^``=` `True` `            ``y ``+``=` `1` `        ``x ``+``=` `1` `     `  `    ``# Mark all multiples of  ` `    ``# squares as non-prime ` `    ``r ``=` `5` `    ``while``(r ``*` `r < limit) : ` `        ``if` `(sieve[r]) : ` `            ``for` `i ``in` `range``(r ``*` `r, limit, r ``*` `r): ` `                ``sieve[i] ``=` `False` `         `  `    ``# Print primes ` `    ``# using sieve[] ` `    ``for` `a ``in` `range``(``5` `, limit ): ` `        ``if` `(sieve[a]): ` `            ``print``(a , end ``=` `" "``) ` ` `  `# Driver Code ` `limit ``=` `20` `SieveOfAtkin(limit) ` ` `  `# This code is contributed ` `# by Smitha `

## C#

 `// C# program for implementation of Sieve ` `// of Atkin ` `using` `System; ` ` `  `class` `GFG { ` ` `  `    ``static` `int` `SieveOfAtkin(``int` `limit) ` `    ``{ ` `        ``// 2 and 3 are known to be prime ` `        ``if` `(limit > 2) ` `            ``Console.Write(2 + ``" "``); ` ` `  `        ``if` `(limit > 3) ` `            ``Console.Write(3 + ``" "``); ` ` `  `        ``// Initialise the sieve array with ` `        ``// false values ` `        ``bool``[] sieve = ``new` `bool``[limit]; ` ` `  `        ``for` `(``int` `i = 0; i < limit; i++) ` `            ``sieve[i] = ``false``; ` ` `  `        ``/* Mark siev[n] is true if one of the ` `        ``following is true: ` `        ``a) n = (4*x*x)+(y*y) has odd number  ` `           ``of solutions, i.e., there exist  ` `           ``odd number of distinct pairs  ` `           ``(x, y) that satisfy the equation  ` `           ``and    n % 12 = 1 or n % 12 = 5. ` `        ``b) n = (3*x*x)+(y*y) has odd number  ` `           ``of solutions and n % 12 = 7 ` `        ``c) n = (3*x*x)-(y*y) has odd number  ` `           ``of solutions, x > y and n % 12 = 11 */` `        ``for` `(``int` `x = 1; x * x < limit; x++) { ` `            ``for` `(``int` `y = 1; y * y < limit; y++) { ` ` `  `                ``// Main part of Sieve of Atkin ` `                ``int` `n = (4 * x * x) + (y * y); ` `                ``if` `(n <= limit && (n % 12 == 1 || n % 12 == 5)) ` ` `  `                    ``sieve[n] ^= ``true``; ` ` `  `                ``n = (3 * x * x) + (y * y); ` `                ``if` `(n <= limit && n % 12 == 7) ` `                    ``sieve[n] ^= ``true``; ` ` `  `                ``n = (3 * x * x) - (y * y); ` `                ``if` `(x > y && n <= limit && n % 12 == 11) ` `                    ``sieve[n] ^= ``true``; ` `            ``} ` `        ``} ` ` `  `        ``// Mark all multiples of squares as ` `        ``// non-prime ` `        ``for` `(``int` `r = 5; r * r < limit; r++) { ` `            ``if` `(sieve[r]) { ` `                ``for` `(``int` `i = r * r; i < limit; ` `                     ``i += r * r) ` `                    ``sieve[i] = ``false``; ` `            ``} ` `        ``} ` ` `  `        ``// Print primes using sieve[] ` `        ``for` `(``int` `a = 5; a < limit; a++) ` `            ``if` `(sieve[a]) ` `                ``Console.Write(a + ``" "``); ` `        ``return` `0; ` `    ``} ` ` `  `    ``// Driver code ` `    ``public` `static` `void` `Main() ` `    ``{ ` `        ``int` `limit = 20; ` `        ``SieveOfAtkin(limit); ` `    ``} ` `} ` ` `  `// This code is contributed by nitin mittal `

## PHP

 ` 2) ` `        ``echo` `2 , ``" "``; ` `    ``if` `(``\$limit` `> 3) ` `        ``echo` `3 , ``" "``; ` ` `  `    ``// Initialise the sieve array  ` `    ``// with false values ` `    ``\$sieve``[``\$limit``] = 0; ` `    ``for` `(``\$i` `= 0; ``\$i` `< ``\$limit``; ``\$i``++) ` `        ``\$sieve``[``\$i``] = false; ` ` `  `    ``/* Mark siev[n] is true if one  ` `       ``of the following is true: ` `    ``a) n = (4*x*x)+(y*y) has odd number of  ` `       ``solutions, i.e., there exist ` `       ``odd number of distinct pairs (x, y)  ` `       ``that satisfy the equation and ` `       ``n % 12 = 1 or n % 12 = 5. ` `    ``b) n = (3*x*x)+(y*y) has odd number of  ` `       ``solutions and n % 12 = 7 ` `    ``c) n = (3*x*x)-(y*y) has odd number of  ` `       ``solutions, x > y and n % 12 = 11 */` `    ``for` `(``\$x` `= 1; ``\$x` `* ``\$x` `< ``\$limit``; ``\$x``++) ` `    ``{ ` `        ``for` `(``\$y` `= 1; ``\$y` `* ``\$y` `< ``\$limit``; ``\$y``++)  ` `        ``{ ` `             `  `            ``// Main part of Sieve of Atkin ` `            ``\$n` `= (4 * ``\$x` `* ``\$x``) + (``\$y` `* ``\$y``); ` `            ``if` `(``\$n` `<= ``\$limit` `&& (``\$n` `% 12 == 1 ||  ` `                                   ``\$n` `% 12 == 5)) ` `                ``\$sieve``[``\$n``] ^= true; ` ` `  `            ``\$n` `= (3 * ``\$x` `* ``\$x``) + (``\$y` `* ``\$y``); ` `            ``if` `(``\$n` `<= ``\$limit` `&& ``\$n` `% 12 == 7) ` `                ``\$sieve``[``\$n``] = true; ` ` `  `            ``\$n` `= (3 * ``\$x` `* ``\$x``) - (``\$y` `* ``\$y``); ` `            ``if` `(``\$x` `> ``\$y` `&& ``\$n` `<= ``\$limit` `&& ` `                            ``\$n` `% 12 == 11) ` `                ``\$sieve``[``\$n``] ^= true; ` `        ``} ` `    ``} ` ` `  `    ``// Mark all multiples of ` `    ``// squares as non-prime ` `    ``for` `(``\$r` `= 5; ``\$r` `* ``\$r` `< ``\$limit``; ``\$r``++) { ` `        ``if` `(``\$sieve``[``\$r``]) { ` `            ``for` `(``\$i` `= ``\$r` `* ``\$r``; ``\$i` `< ``\$limit``; ` `                             ``\$i` `+= ``\$r` `* ``\$r``) ` `                ``\$sieve``[``\$i``] = false; ` `        ``} ` `    ``} ` ` `  `    ``// Print primes  ` `    ``// using sieve[] ` `    ``for` `(``\$a` `= 5; ``\$a` `< ``\$limit``; ``\$a``++) ` `        ``if` `(``\$sieve``[``\$a``]) ` `            ``echo` `\$a` `, ``" "``; ` `} ` ` `  `    ``// Driver Code ` `    ``\$limit` `= 20; ` `    ``SieveOfAtkin(``\$limit``); ` ` `  `// This code is contributed by nitin mittal. ` `?> `

Output:

`2 3 5 7 11 13 17 19 `

How it Works:

1. The algorithm treats 2, 3 and 5 as special cases and just adds them to the set of primes to start with.
2. Like Sieve of Eratosthenes, we start with a list of numbers we want to investigate. Suppose we want to find primes <=100, then we make a list for [5, 100]. As explained in (1), 2, 3 and 5 are special cases and 4 is not a prime.
3. The algorithm talks in terms of modulo-60 remainders. .
4. All numbers with modulo-sixty remainder 1, 13, 17, 29, 37, 41, 49, or 53 have a modulo-twelve remainder of 1 or 5. These numbers are prime if and only if the number of solutions to 4×2+y2=n is odd and the number is squarefree. A square free integer is one which is not divisible by any perfect square other than 1.
5. All numbers with modulo-sixty remainder 7, 19, 31, or 43 have a modulo-six remainder of 1. These numbers are prime if and only if the number of solutions to 3x2 + y2 = n is odd and the number is squarefree.
6. All numbers with modulo-sixty remainder 11, 23, 47, or 59 have a modulo-twelve remainder of 11. These numbers are prime if and only if the number of solutions to 3x2 – y2 = n is odd and the number is squarefree.

Lets see how it generate prime up to 20:

```1    2    3    4    5    6    7    8    9    10
11  12   13    14   15   16   17  18   19    20```

Step 0:
Status for all the numbers in the start is False. Special number is 2, 3 and 5 which are known to be prime.

Step 1:
Generate Values for the conditions.

Step 2:
Flipping the status according to condition.

The above values of n in the table generated in x, y loop will be tested for modulo condition.
Column 1: if (colum1 value) % 12 == 1 or 5
then flip the sieve status for that number.
We are taking mod with 12 in place of 60, this is because if we take mod 60 then we have to consider many r as 1, 13, 17, 29, 37, 41, 49, or 53 and for all these r, mod 12 is 1 or 5. (done only to reduce the expression size)

Column 2: if (colum2 value) % 12 == 7
then flip the sieve status for that number.

Column 3: if (colum3 value) % 12 == 11
then flip the sieve status for that number.

Step 3 :
Checking for Square free Condition: If any number in our list in square of any number then remove it.

Step 4 :
Creating array of prime numbers for which status is true.
i.e. 2 3 5 7 11 13 17 19

Step 5 :
Print the output on the screen.