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
    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).2012-04-06
  • 0
    All numbers, including x and y, are whole numbers (positive integers). what are these x and y ?2012-04-06
  • 0
    Did you try scrolling down to the explanation section of the wiki?2012-04-06
  • 0
    I couldn't be able to understand :( may be by seeing a running example i can get something ...2012-04-06
  • 0
    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?2012-04-06
  • 0
    from the psuedocode for (x, y) in [1, √limit] × [1, √limit]: does it mean in each iteration i need to pick a combination of x and y from [1,√limit(till the number i wanted the prime)] ?2012-04-06
  • 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      }  } 
  • 0
    @Sunny: You are welcome :-)2012-04-06
  • 0
    That is *one* possibility. The general formulation implies that the order does not matter as long as you use each pair exactly once.2012-04-06
  • 0
    @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.2012-04-06
  • 0
    @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.2012-04-06
  • 0
    @Raphael: Order is relevant, and they are taking a cartesian product. What is wrong there?2012-04-06
  • 0
    @Aryabhata: It is a cartesian product of two closed intervals (of integers), which is a set. Sets don't have order. Therefore, the pseudo code's semantic is not the intended one.2012-04-06
  • 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