Linked List 10 operations from which problems are made ( complete guide for you)

// sieve of Atkin is a popular way to find all the prime numbers in range using the dp approach and is //better than the erronthesis approach
// C++ program for implementation of Sieve of Atkin
#include <bits/stdc++.h>
using namespace std;
 
int SieveOfAtkin(int limit)
{
    // 2 and 3 are known to be prime
    if (limit > 2)
        cout << 2 << " ";
    if (limit > 3)
        cout << 3 << " ";
 
    // Initialise the sieve array with false values
    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++) {
             
            // Main part of Sieve of Atkin
            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;
        }
    }
 
    // Mark all multiples of squares as non-prime
    for (int r = 5; r * r < limit; r++) {
        if (sieve[r]) {
            for (int i = r * r; i < limit; i += r * r)
                sieve[i] = false;
        }
    }
 
    // Print primes using sieve[]
    for (int a = 5; a < limit; a++)
        if (sieve[a])
            cout << a << " ";
}
 
// Driver program
int main(void)
{
    int limit = 20;
    SieveOfAtkin(limit);
    return 0;
}
/*
Output:
2 3 5 7 11 13 17 19
How it Works:

The algorithm treats 2, 3 and 5 as special cases and just adds them to the set of primes to start with.
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. .
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.
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.
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.
Lets see how it generate prime up to 20:

1    2    3    4    5    6    7    8    9    10
11  12   13    14   15   16   17  18   19    20
Step 0:
Status for all the numbers in the start is False. Special number is 2, 3 and 5 which are known to be prime.

Step 1:
Generate Values for the conditions.
atkins

Step 2:
Flipping the status according to condition.

The above values of n in the table generated in x, y loop will be tested for modulo condition.
Column 1: if (colum1 value) % 12 == 1 or 5
         then flip the sieve status for that number.
We are taking mod with 12 in place of 60, this is because if we take mod 60 then we have to consider many r as 1, 13, 17, 29, 37, 41, 49, or 53 and for all these r, mod 12 is 1 or 5. (done only to reduce the expression size)

Column 2: if (colum2 value) % 12 == 7
         then flip the sieve status for that number.

Column 3: if (colum3 value) % 12 == 11
         then flip the sieve status for that number.
       

Step 3 :
Checking for Square free Condition: If any number in our list in square of any number then remove it.

Step 4 :
Creating array of prime numbers for which status is true.
i.e. 2 3 5 7 11 13 17 19

Step 5 :
Print the output on the screen.
*/