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

  • $\begingroup$ 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). $\endgroup$ – Aryabhata Apr 6 '12 at 18:02
  • $\begingroup$ All numbers, including x and y, are whole numbers (positive integers). what are these x and y ? $\endgroup$ – Dungeon Hunter Apr 6 '12 at 18:05
  • $\begingroup$ Did you try scrolling down to the explanation section of the wiki? $\endgroup$ – Aryabhata Apr 6 '12 at 18:06
  • $\begingroup$ I couldn't be able to understand :( may be by seeing a running example i can get something ... $\endgroup$ – Dungeon Hunter Apr 6 '12 at 18:08
  • $\begingroup$ 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? $\endgroup$ – Aryabhata Apr 6 '12 at 18:12

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


  • $\begingroup$ @Sunny: You are welcome :-) $\endgroup$ – Aryabhata Apr 6 '12 at 18:35
  • $\begingroup$ That is one possibility. The general formulation implies that the order does not matter as long as you use each pair exactly once. $\endgroup$ – Raphael Apr 6 '12 at 21:38
  • $\begingroup$ @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. $\endgroup$ – Aryabhata Apr 6 '12 at 21:45
  • $\begingroup$ @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. $\endgroup$ – Raphael Apr 6 '12 at 21:49
  • 1
    $\begingroup$ @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. $\endgroup$ – Aryabhata Apr 6 '12 at 21:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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