Posted on by Kalkicode
Code Mathematics

Sieve of Atkin

The Sieve of Atkin is an optimized algorithm for finding prime numbers within a given range. It is an enhancement over the Sieve of Eratosthenes and is designed to efficiently identify prime numbers up to a specified limit. This article presents a C program that implements the Sieve of Atkin algorithm to find and print prime numbers within a given range.

Problem Statement

Given a positive integer 'n', the task is to find and print all prime numbers that are less than or equal to 'n' using the Sieve of Atkin algorithm.

Example

For example, if 'n' is 25, the prime numbers in the range from 2 to 25 are 2, 3, 5, 7, 11, 13, 17, 19, and 23. Similarly, for 'n' as 100, the prime numbers are 2, 3, 5, 7, 11, 13, ..., 97. For 'n' as 200, the prime numbers are 2, 3, 5, 7, 11, 13, ..., 199.

Idea to Solve

The Sieve of Atkin algorithm works by marking numbers in a specific pattern to identify prime numbers. It uses mathematical operations to determine the primality of numbers and efficiently eliminate the non-prime candidates.

Pseudocode

function sieve_of_atkin(n):
    if n <= 1:
        Return
    Create an array 'sieve' of size (n + 1) and initialize all elements to 0
    Loop for x = 1 to sqrt(n):
        Loop for y = 1 to sqrt(n):
            Calculate num1 = 4 * x * x + y * y
            Calculate num2 = 3 * x * x + y * y
            Calculate num3 = 3 * x * x - y * y
            If num1 <= n and num1 % 12 = 1 or 5:
                Toggle sieve[num1]
            If num2 <= n and num2 % 12 = 7:
                Toggle sieve[num2]
            If x > y and num3 <= n and num3 % 12 = 11:
                Toggle sieve[num3]
    Loop for x = 5 to sqrt(n):
        If sieve[x] = 1:
            Loop for y = x^2 to n in steps of x^2:
                Set sieve[y] = 0
    Set sieve[2] = 1
    Set sieve[3] = 1
    Print "All prime of (2 -", n, ") is :"
    Print "[", prime elements marked as 1, "]"

function main():
    sieve_of_atkin(25)
    sieve_of_atkin(100)
    sieve_of_atkin(200)

Algorithm Explanation

  1. The sieve_of_atkin function takes one parameter: 'n'.
  2. It checks if 'n' is less than or equal to 1, and if so, returns without performing any calculations.
  3. It creates an array 'sieve' of size (n + 1) to track whether a number is prime or not.
  4. It initializes all elements of the 'sieve' array to 0.
  5. It iterates through values of 'x' and 'y', calculating num1, num2, and num3 based on the Atkin algorithm's formulae.
  6. It toggles the value of sieve[num1], sieve[num2], and sieve[num3] based on their values and the conditions specified in the algorithm.
  7. It iterates through values of 'x' again and eliminates the multiples of prime numbers using the Atkin algorithm's method.
  8. It sets sieve[2] and sieve[3] to 1 to indicate that they are prime numbers.
  9. It prints the prime elements (marked as 1) within the range (2 - n).

Code Solution

// 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 ]

Time Complexity

The Sieve of Atkin algorithm has a better time complexity than the Sieve of Eratosthenes. It is estimated to have a time complexity of approximately O(n / log log n), making it even more efficient for finding prime numbers.

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.

New Comment