Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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

share|cite|improve this question
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
up vote 2 down vote accepted

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


share|cite|improve this answer
Thanks for your explanation :) – Dungeon Hunter Apr 6 '12 at 18:34
@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
@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

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.