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

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

• What parts don't you understand? ("All of it" is not a valid answer.). This is a Q&A site and not a tutoring site. So if you have a specific question, ask away, otherwise this is off-topic. There might be other such "explain to me" questions, but that is not a reason to ask more of the same kind, especially without first putting in some effort yourself (or at least indicating it). – Aryabhata Apr 6 '12 at 18:02
• All numbers, including x and y, are whole numbers (positive integers). what are these x and y ? – Dungeon Hunter Apr 6 '12 at 18:05
• Did you try scrolling down to the explanation section of the wiki? – Aryabhata Apr 6 '12 at 18:06
• I couldn't be able to understand :( may be by seeing a running example i can get something ... – Dungeon Hunter Apr 6 '12 at 18:08
• As I said, if you have a specific mathematical question regarding the algorithm, you can ask it here. Otherwise it is off-topic for a Q&A site. Why don't you try running an example yourself, and then see where you get stuck and make a specific question out of it? – Aryabhata Apr 6 '12 at 18:12

## 1 Answer

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

}

}

• @Sunny: You are welcome :-) – Aryabhata Apr 6 '12 at 18:35
• That is one possibility. The general formulation implies that the order does not matter as long as you use each pair exactly once. – Raphael Apr 6 '12 at 21:38
• @Raphael: Maybe, but it forms sums of the form $x^2 + 4y^2$, so order might might be relevant. Besides, the question (IMO) is more about interpreting that line, rather than whether we can ignore the order. – Aryabhata Apr 6 '12 at 21:45
• @Aryabhata: If the order is relevant the pseudo code is wrong (read: bad). "How to interpret" means for me "how to code it", so we have to decide for one order and have to know wether the pseudo code allows for it. – Raphael Apr 6 '12 at 21:49
• @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. – Aryabhata Apr 6 '12 at 21:57