Sieve of Atkin

algorithm
mathematical-algorithm
primality-test
prime-number
sieve-of-atkin
(Team) #1

The Sieve of Atkin is an efficient algorithm used to find all prime numbers upto a given number (say N) and does so in O(N) time complexity. With a modified version with enumerating lattice points variation, the time complexity goes to O(N / log log N). Sieve of Atkin is computationally efficient than Sieve of Eratosthenes as it marks multiple of square of prime numbers.

Read this article to understand Sieve of Atkin in depth

Have a doubt or thought? Join the discussion now


This is a companion discussion topic for the original entry at http://iq.opengenus.org/sieve-of-atkin/