How to select the values X and Y in the Sieve Of Atkin Algorithm

Question

I came to know Sieve of Atkin is the fastest algorithm to calculate prime numbers till the given integer. I am able to understand the sieve of Eratosthenes from wikipedia page but i am not able to understand this algorithm from wiki. In wiki the algorithm used two whole numbers x and y how to select those.

From the Psuedo Code

for (x, y) in [1, √limit] × [1, √limit]:

considering limit as the number till which i need the prime numbers.does it mean in each iteration i need to pick a combination of x and y from [1,√limit] ?

Answer 1

Yes, it means you take every possible combination.

$A\times B$ is typically used to denote the cartesian product of two sets.

$$A\times B = \{(a,b) | a \in A, b \in B\}$$

The order in which you enumerate $A\times B$ in this case, does not matter.

So you can actually consider it as two loops, one nested in the other:

for( x = 1; x <= sqrt(limit); x++) {
    for (y = 1 ; y <= sqrt(limit); y++) {

    // The core sieving algorithm

    }

}