1
$\begingroup$

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

  • 0
    Please edit the question :-) (and the title if possible).2012-04-06

1 Answers 1

2

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      }  } 
  • 1
    @Raphael: Oh, you were talking about ordering among the ordered pairs. I was talking about ordering between $x$ and $y$ and whether we need to consider $(x,y)$ and $(y,x)$ as different. No, I believe it does not matter in which order you enumerate the pairs and so we can say for each $(a,b)$ in $A\times B$ without having to worry about correctness.2012-04-06