How does sieve of atkin (modern way to compute prime number up to n) works and what is it's complexity?

Question

Given an unordered array A of size n and integer x. What is the best complexity to find two elements in A whose sum is x?
Share the algo, its complexity and if possible C code.

Answer 1

Hi Shashikant,This algorithm is modification over sieve of eratosthenes that is first we make a set of 2,3 and 5 as these are special cases for sieve of atkin then do operations by making them as a base and the only difference is that we also set "False" to square of primes so that complexity of this algorithm reduces from O(n * log log n) to O(n/log log n).

How this algorithm 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.
The algorithm talks in terms of modulo-60 remainders. .
3.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.
4.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.
5.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.

C++ Program :

#include <bits/stdc++.h>
using namespace std;

int SieveOfAtkin(int limit)
{
    if (limit > 2)  cout << 2 << " ";
    if (limit > 3)  cout << 3 << " ";
    bool sieve[limit];
    for (int i=0; i<limit; i++)
        sieve[i] = false;
    for (int x = 1; x*x < limit; x++)
    {
        for (int y = 1; y*y < limit; y++)
        {
            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;
        }
    }

    for (int r = 5; r*r < limit; r++)
    {
        if (sieve[r])
        {
            for (int i = r*r; i < limit; i += r*r)
                sieve[i] = false;
         }
    }
    for (int a = 5; a < limit; a++)
        if (sieve[a])
           cout << a << " ";
}

int main(void)
{
    int limit = 100;
    SieveOfAtkin(limit);
    return 0;
}

Output: 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

Complexity : O(n/(log log n))