This article is of interest to the following WikiProjects:

Greece Start‑class Mid‑importance This article is within the scope of WikiProject Greece, a collaborative effort to improve the coverage of Greece on Wikipedia. If you would like to participate, please visit the project page, where you can join the discussion and see a list of open tasks.GreeceWikipedia:WikiProject GreeceTemplate:WikiProject GreeceGreek articles Start This article has been rated as Start-class on Wikipedia's content assessment scale. Mid This article has been rated as Mid-importance on the project's importance scale. Classical Greece and Rome Start‑class Mid‑importance This article is within the scope of WikiProject Classical Greece and Rome, a group of contributors interested in Wikipedia's articles on classics. If you would like to join the WikiProject or learn how to contribute, please see our project page. If you need assistance from a classicist, please see our talk page.Classical Greece and RomeWikipedia:WikiProject Classical Greece and RomeTemplate:WikiProject Classical Greece and RomeClassical Greece and Rome articles Start This article has been rated as Start-class on Wikipedia's content assessment scale. Mid This article has been rated as Mid-importance on the project's importance scale. Mathematics Start‑class Mid‑priority This article is within the scope of WikiProject Mathematics, a collaborative effort to improve the coverage of mathematics on Wikipedia. If you would like to participate, please visit the project page, where you can join the discussion and see a list of open tasks.MathematicsWikipedia:WikiProject MathematicsTemplate:WikiProject Mathematicsmathematics articles Start This article has been rated as Start-class on Wikipedia's content assessment scale. Mid This article has been rated as Mid-priority on the project's priority scale.

Archives

Index Archive 1 Archive 2 Archive 3

This page has archives. Sections older than 90 days may be automatically archived by Lowercase sigmabot III when more than 5 sections are present.

Thanks CRGreathouse for correcting my edits. I assume there's some guidance in MOS about using "math" for numbers (though I thought they looked better that way). I have only two issues left: both lead and pseudo-code were actually sourced to Horsley. The wording in lead was almost entirely his, specifically talking about multiples "following" a prime "at regular distances". The reason that should be in a lead is, as it is right now nothing precludes trial division from being accepted as SoE. Marks multiples how? By testing each candidate? Your phrasing allows for that. It is precisely that it marks numbers "at regular distances after the prime", says Horsley, what "the Sieve operation" is. That is his main point he stresses. Do you want a page number? :) (I've put back the short phrase into lead, for now).

Second, the pseudo-code too was sourced to, and following Horsley, who actually did work on odds only from the start, and talked about "each 5th number in [odds] sequence" after "square of 5" being "5's multiple", and stopped when the square reached the top (finally the source for that). That was the reason for my adjusting the pseudo-code to this. So can we please have it back? I removed sourcing to Horsley for now, but I think his code should be back, and reference to Sedgwick "expunged". Cheers, -- WillNess (talk) 08:52, 19 December 2011 (UTC)[reply]

retract on pseudo-code: indeed we once decided to keep it to the bare minimum, for simplicity. WillNess (talk) 09:07, 19 December 2011 (UTC)[reply]

BTW even the table in Nicomachus starts its markings from squares of each odd number; so is this over-simplification our OR perhaps? Do we have any actual RS to it? (bar Sedgewick which is only code without any discussion). WillNess (talk) 09:14, 19 December 2011 (UTC)[reply]

alternative wording: "It does so by gradually marking as composite the (equally spaced) multiples of each prime, starting with 2." Which is better? WillNess (talk) 08:56, 19 December 2011 (UTC)[reply]

I don't think "following a prime at regular distances" is useful or needed, but I'm open to alternate wordings. (I don't think it accomplishes your stated goal, either -- nothing about "at regular distances" precludes trial division, either...)

I hope the wording does not follow Horsley too closely; is this a COPYVIO concern? We can reword if that's an issue.

CRGreathouse (t | c) 01:50, 20 December 2011 (UTC)[reply]

COPYVIO for 1772 material? Really? :) And saying they are at regular distances, or equally spaced, shows they are not tested at all, so would exclude trial division.

What about sources for the oversimplified algorithm description? Horsley claims to be the first after the "dark ages" (his words) to bring the SoE back, and he makes a point of using odds, and squares, etc. The table in Nicomachus seems to suggest the marking of multiples of odds, at equal spaces, starting with their squares, too. So who is saying that Eratosthenes marked from primes, and from primes themselves? What WP:RS shows it that way and attributes it to Eratosthenes? Or at least calls it that? Can you translate what the Greek text is saying? There seem to be something about equal spaces in there too, but from where? WillNess (talk) 08:29, 20 December 2011 (UTC)[reply]

(Heh, good point on the date -- I was just trying to figure out where you were going with "follow closely".)

I wouldn't mind making the odd-only version primary in the article. The all-numbers version is actually quite common pedagogically so it should be mentioned, but it's never really implemented. (I saw a quote one time suggesting that even Eratosthenes wouldn't have written down the even numbers.) I'm happy to follow your preference in this case, unless there's disagreement from others.

I can look at the Greek some time, but not tonight.

I do still disagree with your wording on "equally spaced". Saying that they are equally spaced doesn't say how they're removed any more than omitting that point. I think for brevity and focus it should not be mentioned at that point in the article, but if for some reason we needed to mention it we should do it more explicitly.

CRGreathouse (t | c) 22:09, 20 December 2011 (UTC)[reply]

As it is a tentative description in the lead, its purpose is to hint, to give impression, not to define precisely. The exact definition follows in the article's body. But when it says "found at equal spaces" it alludes to how they are found - i.e. not by testing. That is the intent. (and how they are removed is another matter entirely. A code could find them directly, but remove by value comparison, etc.)

I actually don't have preference, I was following the sources. But there is this tension between making it true, and making it simple. If you could read this Greek text, few key passages from it, that would be great news (or maybe find some other RS). After all it is the algorithm named after Eratosthenes that we describe here, not the algorithm as was invented by him. Does that mean we must find what is the consensus on this among contemporary sources? or just deem this issue insignificant, choose what we please, and move along? This is not the history of mathematics article after all. :) WillNess (talk) 08:35, 21 December 2011 (UTC)[reply]

As for the reason why, I think, this clarification should be in the lead, it is that it is a very common mistake to mix up the two - after all we're removing the multiples right? - so this the essence of the sieve should be clarified right away, somehow. WillNess (talk) 09:34, 21 December 2011 (UTC)[reply]

As compromise between simplicity and being true to the sources, what if we bring back that better pseudo-code based on Horsley, the most recent one that was deleted, and just leave the description as it is, the simplest, for now? Just say yes. :) WillNess (talk) 09:45, 21 December 2011 (UTC)[reply]

Just so I understand: what, to you, is the advantage of the pseudocode you prefer? CRGreathouse (t | c) 14:49, 21 December 2011 (UTC)[reply]

Following more closely the sources we present right now - i.e. Horsley. Plus, it's faster. And on sequential access it even brings down the time complexity significantly.

I'm not so sure about Horsley anymore. He says "having stated what [he] take[s] to have been the genuine theory of Eratosthenes's method", he "deduced from it an operation of great simplicity" and "scruple[s] not to adopt [it] as the original Operation of the Sieve, though nothing like it is to be found in Nicomachus". (??!?) So before we continue, can we find out what N. is saying ?? Probably ask someone Greek-speaking on Project Math to translate it? WillNess (talk) 16:18, 21 December 2011 (UTC)[reply]

I'll see what I can do on Nicomachus. But probably nothing until the end of the holiday season. CRGreathouse (t | c) 17:44, 21 December 2011 (UTC)[reply]

Your newest text,

numbers situated at equal spaces from each prime

seems supremely unhelpful to me. I think that I could ask 10 people (some mathematicians, some not) what that meant and not have a single person guess. I understand that you're concerned that a person might misunderstand how the sieve removes primes but this doesn't explain it either. Can the wording be improved? I'm happy to have text which addresses your concerns but this version is unintelligible.

CRGreathouse (t | c) 15:53, 22 December 2011 (UTC)[reply]

I agree - the previous version was clearer. I have restored it, with some small additions. Gandalf61 (talk) 16:19, 22 December 2011 (UTC)[reply]

Thanks guys, I appreciate teh feedback. WillNess (talk) 19:30, 22 December 2011 (UTC)[reply]

Here's one:

It does so by iteratively marking as composite the multiples of each prime, starting with the multiples of 2, finding the multiples of a given prime directly as members of arithmetic progression with the step equal to that prime, starting from the prime's square.

What's the verdict? WillNess (talk) 19:56, 22 December 2011 (UTC)[reply]

It's an improvement, but still pretty unwieldy. I'll try to think of something that would work here. CRGreathouse (t | c) 00:27, 23 December 2011 (UTC)[reply]

What about this: we leave Gandalf's text where it is (it's an improvement over the version as of my last edit) but add a third paragraph to the lede explaining the sieving process in more detail. This way we can leave the opening straightforward but still address your concern over misinterpretation. We can even do that explicitly: after explaining the procedure we can note the difference between the SoE and other things (e.g. the 'unfaithful sieve') for which it might be mistaken. CRGreathouse (t | c) 00:33, 23 December 2011 (UTC)[reply]

Let's see how it looks. Just better not to use that term, which really is referring just to trial division sieve. And I think the confusion isn't confined just to functional languages - I've seen Python imperative codes a plenty that do the testing. What you mean is basically turning that half-sentence I added into new sentence or two, kind of like this:

In mathematics, the sieve of Eratosthenes (Greek: κόσκινον Ἐρατοσθένους), one of a number of prime number sieves, is a simple, ancient algorithm for finding all prime numbers up to any given limit.[1] It does so by iteratively marking as composite the multiples of each prime, starting with the multiples of 2.[1]

The sieve finds the multiples of a given prime directly as members of arithmetic progression with the step equal to that prime, starting from the prime itself. Thus each composite is found out only from its prime factors. This is the key to the sieve's efficiency, and its key difference from trial division which tests each candidate number for divisibility by its preceding primes, sequentially.

It is one of the most efficient ways to find all of the smaller primes (below 10 million or so).[2] The algorithm is named after Eratosthenes of Cyrene, an ancient Greek mathematician; although none of his works have survived, the sieve was described and attributed to Eratosthenes in the Introduction to Arithmetic by Nicomachus.[3]

(needs more polishing probably, and some sourcing too). WillNess (talk) 08:12, 23 December 2011 (UTC)[reply]

Well... I don't think that's any better. :( "directly as members of arithmetic progression with the step equal to that prime" doesn't seem to elucidate the meaning—"directly" doesn't mean anything unless you already know what's meant. And I think that the sieve is easy enough to understand that many people will read this article who have not heard to term "arithmetic progression" -- I didn't learn that term until high school, years after I first used the SoE. (And plenty of people have graduated HS who couldn't tell you what an arithmetic progression is.) I'm not sure how common "step" (in that sense) is outside of programming, either.

The comparison with trial division is also misleading, IMO. The idea of the sieve is to generate a block of prime numbers, while trial division tests a single number. The implicit comparison the new sentence makes is between running the sieve (once) on a block of numbers vs. running trial division on each of the numbers in that range. It's like saying that a car is less efficient than a train because you'd have to drive back and forth a thousand times to carry as much coal as the train can -- OK, true I suppose, but that's not what cars are for and in any case it's not a key component of cars, certainly not something I'd mention in the lede of Automobile. Better would be to say, "Cars are good at commuting, but not suitable for carrying large shipments of coal, for which a train or ship is more appropriate.", or non-allegoriously "This sieve generates all prime numbers in a given range, unlike trial division which tests a single number. Trial division is much less efficient than the SoE at generating such ranges.". (Wording, of course, is to get the concept across and not [directly] suitable for inclusion.)

CRGreathouse (t | c) 22:57, 23 December 2011 (UTC)[reply]

Well of course it was in the context of finding all prime numbers up to any given limit, it is what the sentence just above it is saying. I think people usually read in context, but this can be clarified. With your other suggestions, the 2nd sentence could be

The sieve finds the multiples of a given prime by enumerating (variant: as) a sequence of numbers such that the difference between the consecutive terms is equal to that prime, counting up from the prime itself. Thus each composite is found out only from its prime factors. This is the key to the sieve's efficiency, and its key difference from using trial division which tests each candidate number for divisibility by its preceding primes, sequentially.

The description in the article body will clarify what questions might remain. WillNess (talk) 01:04, 24 December 2011 (UTC)[reply]

I just don't think that's an improvement over the current state of the article. CRGreathouse (t | c) 00:13, 26 December 2011 (UTC)[reply]

I think it is a significant improvement. Current lead is ambiguous. The proposed change removes this ambiguity. You yourself said this needs to be addressed. Your specific objections that you gave to my previous version, I addressed in this version, and now suddenly you don't give me a specific objections at all but rather go back to the vague and general "I don't like it". Are we having a discussion about content here, or are you amusing yourself here at my expense? It was your idea to expand the lead, now you don't feel like it? Which is it? WillNess (talk) 16:22, 26 December 2011 (UTC)[reply]

I did not -- I said I'm willing to have the article address your concern, not that I share it.

I've already given specific objections. After you dismissed those, I declined to repeat myself.

CRGreathouse (t | c) 15:42, 27 December 2011 (UTC)[reply]

You wrote: "we [should] ... add a third paragraph to the lede explaining the sieving process in more detail". So you did propose expanding the lead, that is what I meant. You brought up valid criticisms of my write-ups, and I did try to address them. What "dismissal" you're talking about? I did re-write that sentence to address your concerns about "arithmetic sequence"; I further re-wrote it to address your concerns about trial division as individual primality check, clarifying that it's "used" in primes range production (that being "the context"). The only dismissal was by you, of my last changes, was my impression.

Look, too many times I've seen it stated that the sieve "removes" the multiples, and there's two problems with that short sentence. Why can't we have a clear explanation in the lead that won't get a reader all confused about it? If that re-write wasn't good enough, how about this one. I tried to clarify and streamline it some more, I really think it's better now:

In mathematics, the sieve of Eratosthenes (Greek: κόσκινον Ἐρατοσθένους), one of a number of prime number sieves, is a simple, ancient algorithm for finding all prime numbers up to any given limit.^[1] It does so by iteratively marking as composite the multiples of each prime number, starting with the multiples of 2.^[1]

The multiples of a given prime are generated as a sequence of equidistant numbers starting from that prime, with a common difference equal to that prime.^[1] Thus each composite is found only from its prime factors. This is the key to the sieve's efficiency, and its key difference from using trial division to test each candidate number for divisibility by its preceding primes, in sequence.^[2]

It is one of the most efficient ways to find all of the smaller primes (below 10 million or so).^[3] The algorithm is named after Eratosthenes of Cyrene, an ancient Greek mathematician; although none of his works have survived, the sieve was described and attributed to Eratosthenes in the Introduction to Arithmetic by Nicomachus.^[4]

What do you think? -- WillNess (talk) 17:49, 27 December 2011 (UTC)[reply]

I think the use of "equidistant numbers", especially linked like that, is confusing. (It makes it seem like there is a property, "equidistant", which some numbers have and some numbers lack.) I think that if there is to be a paragraph describing this, as I suggested, it should be the third paragraph, not the second (also as I suggested) -- more important in the lede is "what does it do" rather than "how does it do it". I think that "this is the key to the sieve's efficiency" needs to be dropped for reasons already discussed. I do like the way the sieve is compared to trial division in this wording. CRGreathouse (t | c) 19:18, 27 December 2011 (UTC)[reply]

I think "equidistant" is just an English word, meaning "of equal distance(s)". I think linking it that way clarifies the meaning, because anyone can click and see exactly what is meant, explained in great detail. But we can drop it if you insist. Same with the order of paragraphs, although "how it does it" here actually defines what it is or is not. According to sources (Horsley, ONeill). Trial division range testing removes the multiples for each prime too, and is NOT the sieve (again the same point). So you might want to reconsider, but whatever. It's up to you. Now for dropping "the key to ... efficiency" - it is really sourced. ONeill spends much time discussing this point (although not in the clearest of verbal formulations, but nevertheless she does so, and with clear math derivations). Plus, it is just a short half-sentence. Plus, I don't understand what reasons were discussed for its being dropped, really I don't know what you mean by that. Wasn't it already addressed with the re-wording about "using the trial division" etc.? Plus, again, it is sourced. So how about this, in the end:

In mathematics, the sieve of Eratosthenes (Greek: κόσκινον Ἐρατοσθένους), one of a number of prime number sieves, is a simple, ancient algorithm for finding all prime numbers up to any given limit.^[1] It does so by iteratively marking as composite the multiples of each prime number, starting with the multiples of 2.^[1]

It is one of the most efficient ways to find all of the smaller primes (below 10 million or so).^[3] The algorithm is named after Eratosthenes of Cyrene, an ancient Greek mathematician; although none of his works have survived, the sieve was described and attributed to Eratosthenes in the Introduction to Arithmetic by Nicomachus.^[4]

The multiples of a given prime are generated as a sequence of numbers starting from that prime, with a common difference between each other, equal to that prime.^[1] Thus each composite is found only from its prime factors. This is the key to the sieve's efficiency, and its key difference from using trial division to test each candidate number for divisibility by its preceding primes, in sequence.^[2]

(I'd still rather prefer the 3rd paragraph to be 2nd here, seems to have better flow that way).

Your feedback? -- WillNess (talk) 22:01, 27 December 2011 (UTC)[reply]

Of course whether a piece of information is sourced or not is a canard—the issue is whether something should be in the lede, not the article. So let's work on the wording.

(paragraphs 1 and 2 as above)

The algorithm starts by considering every number as a possible prime. It then marks off multiples of numbers (it suffices to use multiples of primes) additively, starting from the prime and increasing by steps of the same size. This is unlike trial division which uses division at each step rather than addition.

OK, rough, but you get the idea.

CRGreathouse (t | c) 02:11, 28 December 2011 (UTC)[reply]

Well, to contrast division with addition is to miss the point completely (i.e. will add confusion). First, "each step" of TD sieve is not "each step" of SoE. TD advances along the candidates sequence step by step (testing each candidate vs each prime in sequence of primes, from the lowest up); SoE advances along primes sequence, firing up the multiples generate-and-mark streams. One "step" of SoE uses a lot of additions, one step of TD a lot of divisions, but these are incomparable steps, they are organized totally differently. Both addition and division individual operations are O(1) for the purposes of algorithm complexity analysis, and still SoE beats TD.

No, the key is that TD considers each prime a possible factor of a candidate; SoE "knows" the factors of each candidate, because it works in the reverse direction, generating instead of testing. This is the key. My wording captures/alludes to that. Yours doesn't even use the words "generate" and "test".

I have to say I think my wording is much clearer. The word "additively" may be even more confusing than "equidistant" (and BTW Nicomachus says "ταυτη διαχωριζομεν", at the bottom of p.29, which I take to mean "equally separated"). The word "step" you once dismissed. Mainly, the whole formulation is too detailed for a lead, and introduces too much time with its "starts" and "then" into the eternal math construct (that all numbers which are not composite are prime - and always so). Plus, its first 1.5 sentences repeat what is already said in the 1st paragraph, with superfluous (for a lead) details.

IMO we already have a good lead, nice and short. All is needed is one last short and approximate statement clarifying about generating, not testing the multiples. No need overloading it with extra details which can be expounded upon in the article's body. If the inclusion of "key to the sieve's efficiency" bit is what's keeping you from agreeing on it, let's remove that for now, if that's what it takes to get it finally through.

In fact I'm confident it's OK now to use it in the article, thanks to all your critique and suggestions, and am going to make the edit, simplifying it some more, incorporating your latest suggestions and concerns. Please don't take it as a sign of disrespect, it is not, you helped greatly to improve my initial wording. We've arrived at something here, let's put up the signpost, take a step back, look at it for a while, and continue from there. I apologize for the unilateral action, but this was too long already, for me. Revert if you must, but I hope you'll find that you don't. :) -- WillNess (talk) 19:33, 28 December 2011 (UTC)[reply]

Wow, I was completely ready to revert but that's actually not bad. Needs work, but then what doesn't in this article? CRGreathouse (t | c) 22:09, 28 December 2011 (UTC)[reply]

See, I told you, you helped greatly to bring it to satisfactory level. Cheers, -- WillNess (talk) 13:07, 29 December 2011 (UTC)[reply]

Just a little question Suppose than I find a other way to compute prime number; How can I know and sid thait it is a new d'Eratosthène version or a new stive? i/e what is the mathématical princip of the stieve

Jérôme

01/29/12 18 CET — Preceding unsigned comment added by 88.189.253.171 (talk) 16:24, 28 January 2012 (UTC)[reply]

It would be good if the animation on the right demonstrating the sieve did not loop continuously but stopped after its first run-through. A user could then perform a refresh if they needed another demonstration. Or even better, if the animation could be paused or started on demand. Presently, it is a rude distraction when it is not wanted. — Preceding unsigned comment added by 216.191.216.222 (talk) 01:50, 8 March 2013 (UTC)[reply]

I tend to agree about animations which are distracting and you can't control them. There is a program jsgif which lets you control animated gifs so you can step through them frame by frame.--Salix (talk): 02:41, 8 March 2013 (UTC)[reply]

Wouldn't it be better to use only one color for all primes that have been marked during the algorithm? In the current animation, at the end of the algorithm the result is a mishmash of colors. I think less colors might be better here. Opinions? -- Toshio Yamaguchi 17:32, 17 April 2013 (UTC)[reply]

Actually, the algorithm is marking composites, with the primes being the residuals, however, I agree that it's a mishmash. My feeling is that the first image the readers sees should be one illustrating the naive algorithm (not starting from prime square). That would visually illustrate the pattern of the sieve in a basic sense (with obvious visual patterns) before the more complex optimization (using prime squares) is used, with less obvious patterning. The graphic is supposed to support the reader, not force them to understand that an optimization has been used prior to understanding the basics. Two cents 70.247.167.104 (talk) 01:19, 26 January 2014 (UTC)[reply]

this can be done here Chrisdecorte (talk) 02:15, 24 March 2014 (UTC)[reply]