Sieve of Atkin

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[2] = 1;
	}
	if (n >= 3)
	{
		//set 3 is prime
		sieve[3] = 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[2] = true;
		}
		if (n >= 3)
		{
			//set 3 is prime
			sieve[3] = 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[2] = true;
			}
			if (n >= 3)
			{
				//set 3 is prime
				sieve[3] = 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[2] = true;
		}
		if (n >= 3)
		{
			//set 3 is prime
			sieve[3] = 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[2] = true;
		}
		if ($n >= 3)
		{
			//set 3 is prime
			$sieve[3] = 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[2] = true;
		}
		if (n >= 3)
		{
			//set 3 is prime
			sieve[3] = 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[2] = True
		
		if (n >= 3) :
			# set 3 is prime
			sieve[3] = 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[2] = true
		end
		if (n >= 3)
		
			# set 3 is prime
			sieve[3] = 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[2] = true;
		}
		if (n >= 3)
		{
			//set 3 is prime
			sieve[3] = 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 ]


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.

New Comment







© 2021, kalkicode.com, All rights reserved