# Sieve of Atkin

The Sieve of Atkin is an algorithm for finding all prime numbers up to a certain limit. It was developed by A. O. L. Atkin and Daniel J. Bernstein in 2004, as an improvement on earlier prime sieving algorithms like the Sieve of Eratosthenes.

The main idea behind the Sieve of Atkin is to identify prime numbers using a set of mathematical functions that help to eliminate composite numbers efficiently. The algorithm works by generating a list of candidate primes, and then applying a series of tests to each candidate to determine if it is prime or not.

The Sieve of Atkin uses three mathematical functions to identify primes: the quadratic function, the modulo function, and the greatest common divisor (GCD) function. These functions are used to mark composite numbers in a specific pattern, allowing the algorithm to quickly eliminate them from consideration.

Compared to the Sieve of Eratosthenes, the Sieve of Atkin can be faster for large prime ranges, as it eliminates many composite numbers more efficiently. However, it requires more memory and is more complex to implement.

Overall, the Sieve of Atkin is an interesting algorithm for finding primes, and it demonstrates the power of using mathematical functions to solve computational problems.

Here given code implementation process.

``````// C Program
// Print prime number by using
// Sieve of Atkin
#include <stdio.h>

//Find all prime numbers which have smaller and equal to given number n
void sieve_of_atkin(int n)
{
if (n <= 1)
{
//When n are invalid to prime number
return;
}
//this are used to detect prime numbers
int sieve[n + 1];
// Loop controlling variables
int x = 0;
int y = 0;
//used to get calculated result
int num = 0;
//Set initial all the numbers are non prime
for (x = 0; x <= n; ++x)
{
sieve[x] = 0;
}
for (x = 1; x * x < n; ++x)
{
for (y = 1; y * y < n; ++y)
{
//Calculate 4x²+y²
num = (4 * x * x) + (y * y);
if (num <= n && (num % 12 == 1 || num % 12 == 5))
{
sieve[num] = sieve[num] ^ 1;
}
//Calculate 3x²+y²
num = (3 * x * x) + (y * y);
if (num <= n && num % 12 == 7)
{
sieve[num] = sieve[num] ^ 1;
}
//Calculate 3x²+y²
num = (3 * x * x) - (y * y);
if (x > y && num <= n && num % 12 == 11)
{
sieve[num] = sieve[num] ^ 1;
}
}
}
for (x = 5; x * x <= n; x++)
{
if (sieve[x] == 1)
{
// When x is prime
// Set multiples of squares as non-prime
for (y = x * x; y <= n; y += x * x)
{
sieve[y] = 0;
}
}
}
//set initial 2 prime value
if (n >= 2)
{
//set 2 is prime
sieve = 1;
}
if (n >= 3)
{
//set 3 is prime
sieve = 1;
}
printf("\n All prime of (2 - %d) is :  \n [", n);
//Display prime element
for (x = 0; x <= n; ++x)
{
if (sieve[x] == 1)
{
printf("  %d", x);
}
}
printf("  ]\n");
}
int main()
{
//Test Case
sieve_of_atkin(25);
sieve_of_atkin(100);
sieve_of_atkin(200);
return 0;
}``````

#### Output

`````` All prime of (2 - 25) is :
[  2  3  5  7  11  13  17  19  23  ]

All prime of (2 - 100) is :
[  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  ]

All prime of (2 - 200) is :
[  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  ]``````
``````// Java Program
// Print prime number by using
// Sieve of Atkin
class SieveOfAtkin
{
//Find all prime numbers which have smaller and equal to given number n
public void sieve_of_atkin(int n)
{
if (n <= 1)
{
//When n are invalid to prime number
return;
}
//This are used to detect prime numbers
boolean[] sieve = new boolean[n + 1];
// Loop controlling variables
int x = 0;
int y = 0;
//used to get calculated result
int num = 0;
//Set initial all the numbers are non prime
for (x = 0; x <= n; ++x)
{
sieve[x] = false;
}
for (x = 1;
(x * x) < n; ++x)
{
for (y = 1; y * y < n; ++y)
{
//Calculate 4x²+y²
num = (4 * x * x) + (y * y);
if (num <= n && (num % 12 == 1 || num % 12 == 5))
{
sieve[num] = sieve[num] ^ true;
}
//Calculate 3x²+y²
num = (3 * x * x) + (y * y);
if (num <= n && num % 12 == 7)
{
sieve[num] = sieve[num] ^ true;
}
//Calculate 3x²+y²
num = (3 * x * x) - (y * y);
if (x > y && num <= n && num % 12 == 11)
{
sieve[num] = sieve[num] ^ true;
}
}
}
for (x = 5; x * x <= n; x++)
{
if (sieve[x] == true)
{
// When x is prime
// Set multiples of squares as non-prime
for (y = x * x; y <= n; y += x * x)
{
sieve[y] = false;
}
}
}
//set initial 2 prime value
if (n >= 2)
{
//set 2 is prime
sieve = true;
}
if (n >= 3)
{
//set 3 is prime
sieve = true;
}
System.out.print("\n All prime of (2 - " + n + ") is is : \n [");
//Display prime element
for (x = 0; x <= n; ++x)
{
if (sieve[x] == true)
{
System.out.print(" " + x);
}
}
System.out.print(" ]\n");
}
public static void main(String[] args)
{
SieveOfAtkin obj = new SieveOfAtkin();
//Test Case
obj.sieve_of_atkin(25);
obj.sieve_of_atkin(100);
obj.sieve_of_atkin(200);
}
}``````

#### Output

`````` All prime of (2 - 25) is is :
[ 2 3 5 7 11 13 17 19 23 ]

All prime of (2 - 100) is is :
[ 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 ]

All prime of (2 - 200) is is :
[ 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 ]``````
``````//Include header file
#include <iostream>
using namespace std;

// C++ Program
// Print prime number by using
// Sieve of Atkin

class SieveOfAtkin
{
public:
//Find all prime numbers which have smaller and equal to given number n
void sieve_of_atkin(int n)
{
if (n <= 1)
{
//When n are invalid to prime number
return;
}
//This are used to detect prime numbers
bool sieve[n + 1];
// Loop controlling variables
int x = 0;
int y = 0;
//used to get calculated result
int num = 0;
//Set initial all the numbers are non prime
for (x = 0; x <= n; ++x)
{
sieve[x] = false;
}
for (x = 1;
(x *x) < n; ++x)
{
for (y = 1; y * y < n; ++y)
{
//Calculate 4x²+y²
num = (4 * x * x) + (y * y);
if (num <= n && (num % 12 == 1 || num % 12 == 5))
{
sieve[num] = sieve[num] ^ true;
}
//Calculate 3x²+y²
num = (3 * x * x) + (y * y);
if (num <= n && num % 12 == 7)
{
sieve[num] = sieve[num] ^ true;
}
//Calculate 3x²+y²
num = (3 * x * x) - (y * y);
if (x > y && num <= n && num % 12 == 11)
{
sieve[num] = sieve[num] ^ true;
}
}
}
for (x = 5; (x * x) <= n; x++)
{
if (sieve[x] == true)
{
// When x is prime
// Set multiples of squares as non-prime
for (y = (x * x); y <= n; y += (x * x))
{
sieve[y] = false;
}
}
}
//set initial 2 prime value
if (n >= 2)
{
//set 2 is prime
sieve = true;
}
if (n >= 3)
{
//set 3 is prime
sieve = true;
}
cout << "\n All prime of (2 - " << n << ") is is : \n [";
//Display prime element
for (x = 0; x <= n; ++x)
{
if (sieve[x] == true)
{
cout << " " << x;
}
}
cout << " ]\n";
}
};
int main()
{
SieveOfAtkin obj = SieveOfAtkin();
//Test Case
obj.sieve_of_atkin(25);
obj.sieve_of_atkin(100);
obj.sieve_of_atkin(200);
return 0;
}``````

#### Output

`````` All prime of (2 - 25) is is :
[ 2 3 5 7 11 13 17 19 23 ]

All prime of (2 - 100) is is :
[ 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 ]

All prime of (2 - 200) is is :
[ 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 ]``````
``````//Include namespace system
using System;

// C# Program
// Print prime number by using
// Sieve of Atkin

class SieveOfAtkin
{
//Find all prime numbers which have smaller and equal to given number n
public void sieve_of_atkin(int n)
{
if (n <= 1)
{
//When n are invalid to prime number
return;
}
//This are used to detect prime numbers
Boolean[] sieve = new Boolean[n + 1];
// Loop controlling variables
int x = 0;
int y = 0;
//used to get calculated result
int num = 0;
//Set initial all the numbers are non prime
for (x = 0; x <= n; ++x)
{
sieve[x] = false;
}
for (x = 1;
(x * x) < n; ++x)
{
for (y = 1; y * y < n; ++y)
{
//Calculate 4x²+y²
num = (4 * x * x) + (y * y);
if (num <= n && (num % 12 == 1 || num % 12 == 5))
{
sieve[num] = sieve[num] ^ true;
}
//Calculate 3x²+y²
num = (3 * x * x) + (y * y);
if (num <= n && num % 12 == 7)
{
sieve[num] = sieve[num] ^ true;
}
//Calculate 3x²+y²
num = (3 * x * x) - (y * y);
if (x > y && num <= n && num % 12 == 11)
{
sieve[num] = sieve[num] ^ true;
}
}
}
for (x = 5; x * x <= n; x++)
{
if (sieve[x] == true)
{
// When x is prime
// Set multiples of squares as non-prime
for (y = x * x; y <= n; y += x * x)
{
sieve[y] = false;
}
}
}
//set initial 2 prime value
if (n >= 2)
{
//set 2 is prime
sieve = true;
}
if (n >= 3)
{
//set 3 is prime
sieve = true;
}
Console.Write("\n All prime of (2 - " + n + ") is is : \n [");
//Display prime element
for (x = 0; x <= n; ++x)
{
if (sieve[x] == true)
{
Console.Write("  " + x);
}
}
Console.Write(" ]\n");
}
public static void Main(String[] args)
{
SieveOfAtkin obj = new SieveOfAtkin();
//Test Case
obj.sieve_of_atkin(25);
obj.sieve_of_atkin(100);
obj.sieve_of_atkin(200);
}
}``````

#### Output

`````` All prime of (2 - 25) is is :
[  2  3  5  7  11  13  17  19  23 ]

All prime of (2 - 100) is is :
[  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 ]

All prime of (2 - 200) is is :
[  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 ]``````
``````<?php
// Php Program
// Print prime number by using
// Sieve of Atkin

class SieveOfAtkin
{
//Find all prime numbers which have smaller and equal to given number n
public  function sieve_of_atkin(\$n)
{
if (\$n <= 1)
{
//When n are invalid to prime number
return;
}
//This are used to detect prime numbers
//Set initial all the numbers are non prime
\$sieve = array_fill(0, \$n + 1, false);
// Loop controlling variables
\$x = 0;
\$y = 0;
//used to get calculated result
\$num = 0;
for (\$x = 1;
(\$x * \$x) < \$n; ++\$x)
{
for (\$y = 1; \$y * \$y < \$n; ++\$y)
{
//Calculate 4x²+y²
\$num = (4 * \$x * \$x) + (\$y * \$y);
if (\$num <= \$n && (\$num % 12 == 1 || \$num % 12 == 5))
{
\$sieve[\$num] = \$sieve[\$num] ^ true;
}
//Calculate 3x²+y²
\$num = (3 * \$x * \$x) + (\$y * \$y);
if (\$num <= \$n && \$num % 12 == 7)
{
\$sieve[\$num] = \$sieve[\$num] ^ true;
}
//Calculate 3x²+y²
\$num = (3 * \$x * \$x) - (\$y * \$y);
if (\$x > \$y && \$num <= \$n && \$num % 12 == 11)
{
\$sieve[\$num] = \$sieve[\$num] ^ true;
}
}
}
for (\$x = 5; \$x * \$x <= \$n; \$x++)
{
if (\$sieve[\$x] == true)
{
// When x is prime
// Set multiples of squares as non-prime
for (\$y = \$x * \$x; \$y <= \$n; \$y += \$x * \$x)
{
\$sieve[\$y] = false;
}
}
}
//set initial 2 prime value
if (\$n >= 2)
{
//set 2 is prime
\$sieve = true;
}
if (\$n >= 3)
{
//set 3 is prime
\$sieve = true;
}
echo "\n All prime of (2 - ". \$n .") is is : \n [";
//Display prime element
for (\$x = 0; \$x <= \$n; ++\$x)
{
if (\$sieve[\$x] == true)
{
echo "  ". \$x;
}
}
echo " ]\n";
}
}

function main()
{
\$obj = new SieveOfAtkin();
//Test Case
\$obj->sieve_of_atkin(25);
\$obj->sieve_of_atkin(100);
\$obj->sieve_of_atkin(200);
}
main();``````

#### Output

`````` All prime of (2 - 25) is is :
[  2  3  5  7  11  13  17  19  23 ]

All prime of (2 - 100) is is :
[  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 ]

All prime of (2 - 200) is is :
[  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 ]``````
``````// Node Js Program
// Print prime number by using
// Sieve of Atkin
class SieveOfAtkin
{
//Find all prime numbers which have smaller and equal to given number n
sieve_of_atkin(n)
{
if (n <= 1)
{
//When n are invalid to prime number
return;
}
//This are used to detect prime numbers
//Set initial all the numbers are non prime
var sieve = Array(n + 1).fill(false);
// Loop controlling variables
var x = 0;
var y = 0;
//used to get calculated result
var num = 0;
for (x = 1;
(x * x) < n; ++x)
{
for (y = 1; y * y < n; ++y)
{
//Calculate 4x²+y²
num = (4 * x * x) + (y * y);
if (num <= n && (num % 12 == 1 || num % 12 == 5))
{
sieve[num] = sieve[num] ^ true;
}
//Calculate 3x²+y²
num = (3 * x * x) + (y * y);
if (num <= n && num % 12 == 7)
{
sieve[num] = sieve[num] ^ true;
}
//Calculate 3x²+y²
num = (3 * x * x) - (y * y);
if (x > y && num <= n && num % 12 == 11)
{
sieve[num] = sieve[num] ^ true;
}
}
}
for (x = 5; x * x <= n; x++)
{
if (sieve[x] == true)
{
// When x is prime
// Set multiples of squares as non-prime
for (y = x * x; y <= n; y += x * x)
{
sieve[y] = false;
}
}
}
//set initial 2 prime value
if (n >= 2)
{
//set 2 is prime
sieve = true;
}
if (n >= 3)
{
//set 3 is prime
sieve = true;
}
process.stdout.write("\n All prime of (2 - " + n + ") is is : \n [");
//Display prime element
for (x = 0; x <= n; ++x)
{
if (sieve[x] == true)
{
process.stdout.write("  " + x);
}
}
process.stdout.write(" ]\n");
}
}

function main()
{
var obj = new SieveOfAtkin();
//Test Case
obj.sieve_of_atkin(25);
obj.sieve_of_atkin(100);
obj.sieve_of_atkin(200);
}
main();``````

#### Output

`````` All prime of (2 - 25) is is :
[  2  3  5  7  11  13  17  19  23 ]

All prime of (2 - 100) is is :
[  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 ]

All prime of (2 - 200) is is :
[  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 ]``````
``````#  Python 3 Program
#  Print prime number by using
#  Sieve of Atkin

class SieveOfAtkin :
# Find all prime numbers which have smaller and equal to given number n
def sieve_of_atkin(self, n) :
if (n <= 1) :
# When n are invalid to prime number
return

# This are used to detect prime numbers
# Set initial all the numbers are non prime
sieve = [False] * (n + 1)
#  Loop controlling variables
x = 0
y = 0
# used to get calculated result
num = 0
x = 1
while ((x * x) < n) :
y = 1
while (y * y < n) :
# Calculate 4x²+y²
num = (4 * x * x) + (y * y)
if (num <= n and(num % 12 == 1 or num % 12 == 5)) :
sieve[num] = sieve[num] ^ True

# Calculate 3x²+y²
num = (3 * x * x) + (y * y)
if (num <= n and num % 12 == 7) :
sieve[num] = sieve[num] ^ True

# Calculate 3x²+y²
num = (3 * x * x) - (y * y)
if (x > y and num <= n and num % 12 == 11) :
sieve[num] = sieve[num] ^ True

y += 1

x += 1

x = 5
while (x * x <= n) :
if (sieve[x] == True) :
#  When x is prime
#  Set multiples of squares as non-prime
y = x * x
while (y <= n) :
sieve[y] = False
y += x * x

x += 1

# set initial 2 prime value
if (n >= 2) :
# set 2 is prime
sieve = True

if (n >= 3) :
# set 3 is prime
sieve = True

print("\n All prime of (2 - ", n ,") is is : \n [", end = "")
# Display prime element
x = 0
while (x <= n) :
if (sieve[x] == True) :
print("  ", x, end = "")

x += 1

print(" ]\n", end = "")

def main() :
obj = SieveOfAtkin()
# Test Case
obj.sieve_of_atkin(25)
obj.sieve_of_atkin(100)
obj.sieve_of_atkin(200)

if __name__ == "__main__": main()``````

#### Output

`````` All prime of (2 -  25 ) is is :
[   2   3   5   7   11   13   17   19   23 ]

All prime of (2 -  100 ) is is :
[   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 ]

All prime of (2 -  200 ) is is :
[   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 ]``````
``````#  Ruby Program
#  Print prime number by using
#  Sieve of Atkin

class SieveOfAtkin

# Find all prime numbers which have smaller and equal to given number n
def sieve_of_atkin(n)

if (n <= 1)

# When n are invalid to prime number
return
end
# This are used to detect prime numbers
# Set initial all the numbers are non prime
sieve = Array.new(n + 1) {false}
#  Loop controlling variables
x = 0
y = 0
# used to get calculated result
num = 0
x = 1
while ((x * x) < n)

y = 1
while (y * y < n)

# Calculate 4x²+y²
num = (4 * x * x) + (y * y)
if (num <= n && (num % 12 == 1 || num % 12 == 5))

sieve[num] = sieve[num] ^ true
end
# Calculate 3x²+y²
num = (3 * x * x) + (y * y)
if (num <= n && num % 12 == 7)

sieve[num] = sieve[num] ^ true
end
# Calculate 3x²+y²
num = (3 * x * x) - (y * y)
if (x > y && num <= n && num % 12 == 11)

sieve[num] = sieve[num] ^ true
end
y += 1
end
x += 1
end
x = 5
while (x * x <= n)

if (sieve[x] == true)

#  When x is prime
#  Set multiples of squares as non-prime
y = x * x
while (y <= n)

sieve[y] = false
y += x * x
end
end
x += 1
end
# set initial 2 prime value
if (n >= 2)

# set 2 is prime
sieve = true
end
if (n >= 3)

# set 3 is prime
sieve = true
end
print("\n All prime of (2 - ", n ,") is is : \n [")
# Display prime element
x = 0
while (x <= n)

if (sieve[x] == true)

print("  ", x)
end
x += 1
end
print(" ]\n")
end
end
def main()

obj = SieveOfAtkin.new()
# Test Case
obj.sieve_of_atkin(25)
obj.sieve_of_atkin(100)
obj.sieve_of_atkin(200)
end
main()``````

#### Output

`````` All prime of (2 - 25) is is :
[  2  3  5  7  11  13  17  19  23 ]

All prime of (2 - 100) is is :
[  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 ]

All prime of (2 - 200) is is :
[  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 ]
``````
``````// Scala Program
// Print prime number by using
// Sieve of Atkin

class SieveOfAtkin
{
//Find all prime numbers which have smaller and equal to given number n
def sieve_of_atkin(n: Int): Unit = {
if (n <= 1)
{
//When n are invalid to prime number
return;
}
//This are used to detect prime numbers
//Set initial all the numbers are non prime
var sieve: Array[Boolean] = Array.fill[Boolean](n + 1)(false);
// Loop controlling variables
var x: Int = 0;
var y: Int = 0;
//used to get calculated result
var num: Int = 0;
x = 1;
while ((x * x) < n)
{
y = 1;
while (y * y < n)
{
//Calculate 4x²+y²
num = (4 * x * x) + (y * y);
if (num <= n && (num % 12 == 1 || num % 12 == 5))
{
sieve(num) = sieve(num) ^ true;
}
//Calculate 3x²+y²
num = (3 * x * x) + (y * y);
if (num <= n && num % 12 == 7)
{
sieve(num) = sieve(num) ^ true;
}
//Calculate 3x²+y²
num = (3 * x * x) - (y * y);
if (x > y && num <= n && num % 12 == 11)
{
sieve(num) = sieve(num) ^ true;
}
y += 1;
}
x += 1;
}
x = 5;
while (x * x <= n)
{
if (sieve(x) == true)
{
// When x is prime
// Set multiples of squares as non-prime
y = x * x;
while (y <= n)
{
sieve(y) = false;
y += x * x;
}
}
x += 1;
}
//set initial 2 prime value
if (n >= 2)
{
//set 2 is prime
sieve(2) = true;
}
if (n >= 3)
{
//set 3 is prime
sieve(3) = true;
}
print("\n All prime of (2 - " + n + ") is is : \n [");
//Display prime element
x = 0;
while (x <= n)
{
if (sieve(x) == true)
{
print("  " + x);
}
x += 1;
}
print(" ]\n");
}
}
object Main
{
def main(args: Array[String]): Unit = {
var obj: SieveOfAtkin = new SieveOfAtkin();
//Test Case
obj.sieve_of_atkin(25);
obj.sieve_of_atkin(100);
obj.sieve_of_atkin(200);
}
}``````

#### Output

`````` All prime of (2 - 25) is is :
[  2  3  5  7  11  13  17  19  23 ]

All prime of (2 - 100) is is :
[  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 ]

All prime of (2 - 200) is is :
[  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 ]``````
``````// Swift Program
// Print prime number by using
// Sieve of Atkin

class SieveOfAtkin
{
//Find all prime numbers which have smaller and equal to given number n
func sieve_of_atkin(_ n: Int)
{
if (n <= 1)
{
//When n are invalid to prime number
return;
}
//This are used to detect prime numbers
//Set initial all the numbers are non prime
var sieve: [Bool] = Array(repeating: false, count: n + 1);
// Loop controlling variables
var x: Int = 0;
var y: Int = 0;
//used to get calculated result
var num: Int = 0;
x = 1;
while ((x * x) < n)
{
y = 1;
while (y * y < n)
{
//Calculate 4x²+y²
num = (4 * x * x) + (y * y);
if (num <= n && (num % 12 == 1 || num % 12 == 5))
{
sieve[num] = sieve[num] != true;
}
//Calculate 3x²+y²
num = (3 * x * x) + (y * y);
if (num <= n && num % 12 == 7)
{
sieve[num] = sieve[num] != true;
}
//Calculate 3x²+y²
num = (3 * x * x) - (y * y);
if (x > y && num <= n && num % 12 == 11)
{
sieve[num] = sieve[num] != true;
}
y += 1;
}
x += 1;
}
x = 5;
while (x * x <= n)
{
if (sieve[x] == true)
{
// When x is prime
// Set multiples of squares as non-prime
y = x * x;
while (y <= n)
{
sieve[y] = false;
y += x * x;
}
}
x += 1;
}
//set initial 2 prime value
if (n >= 2)
{
//set 2 is prime
sieve = true;
}
if (n >= 3)
{
//set 3 is prime
sieve = true;
}
print("\n All prime of (2 - ", n ,") is is : \n [", terminator: "");
//Display prime element
x = 0;
while (x <= n)
{
if (sieve[x] == true)
{
print("  ", x, terminator: "");
}
x += 1;
}
print(" ]\n", terminator: "");
}
}
func main()
{
let obj: SieveOfAtkin = SieveOfAtkin();
//Test Case
obj.sieve_of_atkin(25);
obj.sieve_of_atkin(100);
obj.sieve_of_atkin(200);
}
main();``````

#### Output

`````` All prime of (2 -  25 ) is is :
[   2   3   5   7   11   13   17   19   23 ]

All prime of (2 -  100 ) is is :
[   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 ]

All prime of (2 -  200 ) is is :
[   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 ]``````

The time complexity of the Sieve of Atkin algorithm is O(n / log log n) for finding all primes up to n. This is an improvement over the Sieve of Eratosthenes, which has a time complexity of O(n log log n) for the same task.

The Sieve of Atkin achieves this better time complexity by using a more sophisticated set of mathematical rules to identify potential primes, and by avoiding unnecessary checks for composite numbers.

The main computational step in the Sieve of Atkin is the sieving itself, which involves looping through all possible values of x and y up to the square root of n. This takes O(sqrt(n)) time. For each value of x and y, the algorithm performs a constant number of operations to check whether a given number is prime or composite. Therefore, the total number of operations is proportional to the number of potential primes found, which is roughly proportional to n / log log n.

Note that the actual running time of the algorithm may depend on implementation details, such as the efficiency of memory access and the use of optimization techniques such as bit-twiddling or parallelization.

## Comment

Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.