Talk:Sieve of Eratosthenes/Archive 3

Archive 1

Archive 2

Archive 3

Symbolic formulas: a recap

In the sections Incremental sieve and Trial division of the article two algorithms are discussed as presented in M. O'Neill article "The Genuine Sieve of Eratosthenes". Inclusion of two symbolic formulas in the article, for illustrative purposes, was proposed (by me) in the thread above, corresponding to the two code fragments as published in the article, in addition to their verbal description. The current state of discussion is as follows.

To recap, the two Haskell code fragments (pp. 10, 3 of the article) are:

primes = 2:([3..] `minus` composites)
composites = union [multiples p | p <- primes]
multiples p = map (*p) [p..]

(this one by Richard Bird) and

primes = 2 : [x | x <- [3..], isprime x]
isprime x = all (\p -> x ‘mod‘ p > 0) (factorsToTry x)
  where
    factorsToTry x = takeWhile (\p -> p*p <= x) primes

The proposed formulas are:

$\textstyle \mathbb {S} \,=\{2\}\bigcup \,(\mathbb {N} _{3}\setminus \bigcup _{p\in \mathbb {S} }\{np:n\in \mathbb {N} _{p}\})$   where   $\mathbb {N} _{m}=\{n\in \mathbb {N} :n\geq m\}$  

$\textstyle \mathbb {T} =\{2\}\bigcup \,\{n\in \mathbb {N} _{3}:(\forall p\in \mathbb {T} )(p^{2}\leq n\Rightarrow p\nmid n)\}$

or I'd rather prefer the arguably equivalent

$\textstyle \mathbb {S} \,=\mathbb {N} _{2}\setminus \bigcup _{p\in \mathbb {S} }\{np:n\in \mathbb {N} _{p}\}$

$\textstyle \mathbb {T} =\{n\in \mathbb {N} _{2}:(\not \exists p\in \mathbb {T} )(p\leq {\sqrt {n}}\land p\mid n)\}$

That the first pair of formulas is a direct translation of the published code (and thus not OR) is self-evident, IMO. I contend that their inclusion would be beneficial to the article, exposing in a succinct manner the two algorithm's similarities and differencies, making them apparent at a glance. Here's how it'd look like, using the first pair of formulas.

Another editor (CRGreathouse) opposes the inclusion, citing (as far as I understand) (a) "impredicativity" of both formulas, because of their self-referential nature (which I claim does not apply as no vicious circle is present here, and is anyway a direct translation of published material), (b) "non-standard notation" without giving any details (presumably referring to (a)), (c) the two formulas "denoting the same idea ("consider only numbers at least 2") " (?? This seems to omit essential parts in the two formulas. It's akin to claiming both 2·3 and 2+2+2 denote the same idea) and (d) not representing the timing concerns (which obviously only code itself could do, but any Haskell code inclusion is also opposed by same editor and several others).

So far this issue had comments from only two editors. I'd like to put this matter to rest, and for that we need to receive opinions from more editors. Will also solicit comments from WikiProject Mathematics and/or Computer science. Please make your comments here.

In particular, do you (1) support inclusion of the 1st pair of formulas, (2) 2nd pair, (3) oppose their inclusion (please suggest any improvements) or (4) oppose inclusion of any kind of symbolic formulas (and if so, what then can be used to give any kind of visual cue to the reader in addition to the purely verbal descriptions) ?

Any opinions will be greatly appreciated. WillNess (talk) 13:00, 22 August 2011 (UTC)

Just a well meaning question: Who do you envision to be the readership of this article? The proposed formulas are very technical, and unintelligible by about 99.9% of the general readership of wikipedia.TR 13:39, 22 August 2011 (UTC)

All kinds of people. For instance, I'm not a mathematician but the notation is readily comprehensible to me. It is always good to give a reader something to explore further IMO; if it is really unknown to the 99.9% of readership, maybe a link to set-builder notation should also be somehow provided. Any reasonably intelligent reader would then be able to learn new stuff for themselves, and be rewarded for it with a new outlook on the two algorithms. This is my intention in having the two formulas there anyway. And if not, no harm in just skipping over them. WillNess (talk) 13:49, 22 August 2011 (UTC)

This is not set-builder notation. I oppose the inclusion of non-standard self-referential variants of this established notation unless sources that directly support this transliteration of the Haskell code can be supplied. Sławomir Biały (talk) 14:35, 22 August 2011 (UTC)

I see no value in including these complex formulas. I can not imagine anyone who would be led to a better understanding of the subject matter by contemplation of the formulas. I have never seen any formulas like this in the mathematical literature, and I think this discussion should be closed until someone produces such a citation. —Mark Dominus (talk) 15:37, 22 August 2011 (UTC) Addendum: I see now that CRGreathouse made the same points already. I am in agreement with everything that CRGreathouse said at greater length above, and I hope you will abandon this ill-conceived project. —Mark Dominus (talk) 15:46, 22 August 2011 (UTC)

All I did was to ask for opinions of others. I have no way of knowing whether it is ill-conceived or otherwise, while seeing only one person's opinion. I said I wanted "to put this matter to rest" didn't I? No need for hurtful formulations here. WillNess (talk) 19:58, 22 August 2011 (UTC)

Even if it's a translation of a published formula, there is sufficient difference to call this OR; changing pseudocode to something that's not pseudocode is a significant change. In any case, multiple version of code, formulas, etc. are not encyclopedic. The most important thing is to explain the algorithm in prose, pseudocode can be provided as aid to understanding as well, but it's not the focus. Translation of pseudocode into a cryptic formulas has no place here.--RDBury (talk) 16:27, 22 August 2011 (UTC)

The problem I tried to address was that any inclusion of Haskell code was deemed inappropriate in a previous discussion (it wasn't pseudocode BTW, but actual executable Haskell code). So it's about having anything at all besides just prose, in the article. It's not "multiple versions", but rather no versions at all right now. The (unsourced) pseudocode that's in the article is about the basic variant of the algorithm, not about these two.

Would you support inclusion of the two source code fragments instead perhaps, or do you consider Haskell "cryptic" as well? (it's not "scare quotes" here, I'm just quoting others in this thread). The majority of opinion so far was against including any Haskell code.

I'd prefer the 2nd set of formulas, I still consider them illustrative and clear-cut, but as they are themselves derived from the 1st pair, they are even deeper in the OR territory apparently. WillNess (talk) 19:58, 22 August 2011 (UTC)

Haskell code is also rather cryptic for the general reader, unfortunately.TR 21:48, 22 August 2011 (UTC)

Both pairs of formulas are cryptic and unlikely to be helpful to anyone. --Joel B. Lewis (talk) 18:12, 22 August 2011 (UTC)

Thank you to everyone for your feedback. So apparently the formulas are cryptic, in non-standard notation, and in need of RS. WillNess (talk) 19:58, 22 August 2011 (UTC)

Discussion of removal of mnemonic

“ Sift the Two's and Sift the Three's,
The Sieve of Eratosthenes.
When the multiples sublime,
The numbers that remain are Prime. ” — Traditional,

Mnemonic verse subsection has been here for ages, is in long standing consensus. Is widely known and cited folklore, old talk page had tons of discussions with refs, shouldn't be removed unilaterally. Reinstated. WillNess (talk) 23:42, 5 October 2011 (UTC)

I don't think there's any value to including it, nor do I think that there's any kind of consensus to keep it. But feel free to convince me. CRGreathouse (t | c) 13:53, 6 October 2011 (UTC)

You got it all backwards as usual. It is you that needs to convince the editors of this page in changing what was long in consensus here. Your editing habits are really disruptive. WillNess (talk) 16:13, 6 October 2011 (UTC)

Presence is not consensus. Shall we take this to WPM, or do you have a better suggestion? CRGreathouse (t | c) 18:41, 6 October 2011 (UTC)

Never mind, I just left a quick note there. CRGreathouse (t | c) 18:51, 6 October 2011 (UTC)

I would say remove it, or leave it out. I don't know that it's widely known as I've never seen it before. It's not notable itself as e.g. part of some larger work such as a verse from some famous poem or poet, and certainly doesn't tell you how to carry out the sieve.--JohnBlackburne^words_deeds 19:45, 6 October 2011 (UTC)

It doesn't appear to be cited to a reliable source. Did I misunderstand the citations? —Mark Dominus (talk) 19:36, 6 October 2011 (UTC) (My real question is whether this is some longstanding piece of well-known folklore, or whether it is something that someone made up on a wiki a couple of years ago. —Mark Dominus (talk) 19:39, 6 October 2011 (UTC))

This is a necessary but not sufficient condition. I don't think it belongs in the article (it's not encyclopedic) regardless of whether it can be sourced or not.

I'm not actually particularly opposed, but I don't see any benefit to keeping it around.

CRGreathouse (t | c) 19:47, 6 October 2011 (UTC)

I agree that at present there does not seem to be much value to including it. —Mark Dominus (talk) 20:00, 6 October 2011 (UTC)

I third that, mnemonics aren't facts that can be sourced and are rarely noteworthy. If it's something that appears appears frequently in popular culture then it may have encyclopedic value, but there aren't many such cases. If the source is under copyright then there is a risk of COPYVIO issues.--RDBury (talk) 23:36, 6 October 2011 (UTC)

As a matter of fact, yes it is a longstanding piece of well-known folklore that appear frequently in popular culture, all you had to do to find this out was to make one simple Google search (which returns "approximately 122,000 results" for "sift the twos and sift the threes" phrase search), but of course you people (and by that I mean haughty erhm highly knowledgeable expert mathematicians) couldn't be bothered with such a lowly minutia as making even one sample search before passing high judgment on the matter. That rhyme's presence here was in longstanding consensus, its "presence" a matter of long debate on the talk page to which I clearly pointed out. Ain't it great to be able to dismiss something on a whim and feel great about it! Let's see if any of you non-editors of this page who jumped in with their carefully-weighed approval will recognize your error and restore it on the page, though I'm not too hopeful about that. WillNess (talk) 11:43, 9 October 2011 (UTC)

Very approximately. If you use the arrows at the bottom of the page to navigate through the search results it stops at 36, or at least it did for me, some of which are WP mirrors.--JohnBlackburne^words_deeds 11:54, 9 October 2011 (UTC)

Here is one: Programming in Prolog by William F. Clocksin, Christopher S. Mellish, "Originally published in 1981, this was the first textbook on programming in the Prolog language and is still the definitive introductory text on Prolog." ... "7.10 Sift the Twos and Sift the Threes, p.174".

So you see, this verse was well enough known indeed since before 1981 to be included in this "definitive" book. QED. WillNess (talk) 12:09, 9 October 2011 (UTC)

Moreover, the book cites the verse in its archaic spelling: "Sift the Two's and Sift the Three's". This was the point discussed at length here on talk page and in the end it was decided to go with the more modern spelling. But as is clearly evidenced by this archaic one the origins of the verse go much back in time. Since this answers in the affirmative questions of at least two of the participants here, and the source is above and beyond reliable and respectable (as pertaining its well-known folklore status), I will reinstate the verse myself shortly with the new attribution. WillNess (talk) 12:25, 9 October 2011 (UTC)

But four out of the five who have voiced their opinions here (that is, all but you) have said that even if sourced the material should not remain—it's insufficiently important or notable.

See also RDBury's comment on Wikipedia talk:WikiProject Mathematics.

CRGreathouse (t | c) 16:58, 9 October 2011 (UTC)

Sadly, it appears that this great little poem (although I'd hardly call it a "mnemonic") has now vanished. If it were to reappear, no doubt the abolitionists would delete it once more.

But worry not - it has been rescued and is happy in its new home on ProofWiki. --Matt Westwood 17:52, 9 October 2011 (UTC)

HERE you go, another vote for it to be kept! Clearly there's NO CONCENSUS for its removal. (to Matt Westwood - please note its attribution to Clocksin and Mellish 1981 book which uses its archaic spelling.) WillNess (talk) 18:06, 9 October 2011 (UTC)

ProofWiki ain't Wikipedia and doesn't live by the same rules - there is no requirement for sources to be cited for material to be included. But if it helps your cause, I'll do that.

If it requires a vote, then it gets my vote. But it should not, not, not, NOT require a vote to include it or not - THERE IS A RELIABLE SECONDARY SOURCE!!!!!!!!!!! --Matt Westwood 18:29, 9 October 2011 (UTC)

No, all four said no such thing. You have a faulty perception. It was you that said that proper attribution to RS is necessary but not sufficient. Out of the four participants besides me, one asked whether it was a longstanding piece of well-known folklore, and another if it appears frequently in popular culture. To which both questions the answer is an emphatic yes. So no grounds for it removal other than your minimalist personal preference. At the very least we don't have a consensus for its removal, because its presence was in long standing consensus. Stop being such a unilateralist and be a team player for once. That means, put your personal ego aside, for once.

Why do I say this? Because I see no other reason for your actions. You brought up two arguments for the removal, that it adds nothing and is badly sourced. Second I debunked, and first is a matter of your personal taste, disputed by me. It does add much liveliness to the page. This is not some highly advanced material here, it is elementary and must be accessible to - and is accessed by scores, no doubt, of - non-mathematicians. And, I emphasize it again, you are in breach of long-standing consensus. The guests' opinions here where based on faulty data, and thus evidently half-baked.

Bottom line: you haven't reached consensus for the removal of material in long-standing consensus. That means you are in breach of WP guidelines. I expect you to correct this and return the material you've removed, until the informed discussion reaches consensus on the matter. WillNess (talk) 18:02, 9 October 2011 (UTC)

And, RDBury's concerns are addressed by the new RS of 1981 textbook. In fact, I read his comments as a vote TO KEEP in light of this. WillNess (talk) 18:23, 9 October 2011 (UTC)

There is no such thing as "long-standing consensus". See WP:Consensus#Consensus can change. In particular 'consensus is not immutable. Past decisions are open to challenge and are not binding. Moreover, such changes are often reasonable. Thus, "according to consensus" and "violates consensus" are not valid rationales for accepting or rejecting proposals or actions. ' (my emphasis).--JohnBlackburne^words_deeds 18:15, 9 October 2011 (UTC)

Great, let's have a new consensus! Previous discussion is null in light of new RS: 1981 Clocksin and Mellish "Programming in Prolog", an authoritative textbook, which has a section titled, "Sift the Two's and Sift the Three's" (note the archaic spelling). REVOTE is called for here. So far I count 2 votes TO KEEP. WillNess (talk) 18:26, 9 October 2011 (UTC)

Two? Which two?

Regardless, I preempted this when I asked for opinions assuming that the material was sourced properly in my 19:47, 6 October 2011 comment. This was addressed to the only editor whose objection was the sourcing, who then agreed that aside from the sourcing the material should not be included. So I still count 1 for inclusion and 4 against. CRGreathouse (t | c) 18:30, 9 October 2011 (UTC)

Also note that JohnBlackburne has removed the poem after your comments, so I think his position is clear. CRGreathouse (t | c) 18:32, 9 October 2011 (UTC)

Which two? Mine and Matt Westwood's. So you do have a problem with perception. Or do you mean to say that my vote doesn't count and your vote is more equal than mine? So if he removed it, we have now 2 to kepp, and 2 to remove. WillNess (talk) 18:37, 9 October 2011 (UTC)

And new votes must be cast in light of new reliable secondary source. You are not the authority on how to interpret the others' votes. They need to cast theirs themselves in light of new evidence, not some speculative argument of yours. WillNess (talk) 18:45, 9 October 2011 (UTC)

You can't simply invalidate others' votes! That's ridiculous. You're right that I had missed Matt Westwood's second comment, though; that's 4 to remove and 2 to keep. CRGreathouse (t | c) 18:51, 9 October 2011 (UTC)

New reliable secondary source invalidates their votes when they explicitly made references to the lack thereof. You can't invalidate their concerns with your speculative arguments. 2 FOR and 2 AGAINST is NOT A CONSENSUS. WillNess (talk) 18:58, 9 October 2011 (UTC)

Actually you're quite wrong in your assertion. Only Mark had mentioned that as the reason for his vote, and only in his first comment. In his second, when I explicitly asked about their merit without respect to sourcing, he still supported removing it. Further, I've already explained this to you. So I can only assume you are ignoring opinions that don't agree with your own. CRGreathouse (t | c) 19:06, 9 October 2011 (UTC)

WRONG. RDBury explicitly refers to the perceived lack of reliable secondary sources (in his comments on Wikipedia talk:WikiProject Mathematics I mean). In light of new evidence, there should be a REVOTE, clearly. WillNess (talk) 19:11, 9 October 2011 (UTC)

• Comment. Why does anyone really care? This is a silly thing to argue about, one way or the other. Spend your time doing something more productive elsewhere! Sławomir Biały (talk) 18:38, 9 October 2011 (UTC)

Because we want it kept. here is no reason for its removal, it has RS, adds greatly to the liveliness and overall tone of the page. Is well known and cited. WillNess (talk) 18:45, 9 October 2011 (UTC)

It makes the article worse, is not encyclopedic, and is opposed by a strong consensus of editors. It should stay removed. CRGreathouse (t | c) 18:51, 9 October 2011 (UTC)

You shouldn't be so dismissive about the opinion of 2 out of 4 editors (so far). What kind of "strong consensus" is that??? This is not very friendly. Is it only the opinions that you like that count? WillNess (talk) 18:56, 9 October 2011 (UTC)

Two editors have said it should be kept against four who've said it should be removed, so there is a consensus to remove it.--JohnBlackburne^words_deeds 18:59, 9 October 2011 (UTC)

(edit conflict) I'm not dismissing them, just pointing out that a 66% supermajority is not tiny (especially when a plurality would suffice). And I think it's funny that you would accuse me of counting only opinions that I like when you decided (not that that counted for anything) to invalidate all votes except for the two that supported your position in your 18:26, 9 October 2011 comment. (It's true, I missed one implicit vote in my tally, but I quickly corrected this.) CRGreathouse (t | c) 19:03, 9 October 2011 (UTC)

66% is "super" majority in your dreams. And WP:CONSENSUS explicitly states that consensus is not decided by ANY kind of majority. WillNess (talk) 19:05, 9 October 2011 (UTC)

As for the votes, I counted the ones explicitly cast at that point in time after the new RS was brought up. WillNess (talk) 19:09, 9 October 2011 (UTC)

See Supermajority, where that exact level is the example used in the lede (as well as further in the text). CRGreathouse (t | c) 19:07, 9 October 2011 (UTC)

(Irrelevant. WP is not parliamentary democracy, and WP:CONSENSUS is not by a majority built.) WillNess (talk) 22:10, 9 October 2011 (UTC)

Quite relevant: your comment regarding supermajorities was wrong. I agree that having a majority does not itself suffice for consensus, but it does move the burden of proof to you—and you haven't shown that you have any sort of consensus. CRGreathouse (t | c) 22:58, 9 October 2011 (UTC)

Although this is now moot (hopefully) my comment did not regard parliamentary supermajorities at all. I was commenting on claimed "super" majority in WP consensus-building discussions, where 66% is no "super" anything, and if at all, shows that neither party has consensus. WillNess (talk) 18:25, 11 October 2011 (UTC)

"It makes the article worse" is WP:IDONTLIKEIT and therefore is an invalid argument to use in a keep/delete debate. Whether you like it or not, it has a reference. I believe that 6 is probably too small a sample to make a decision on. But its presence / absence on the page should not be done on a voting system - if its notable, and there are references, then there is no reason for it to be deleted. "It's not encyclopedic" - I would suggest it is encyclopedic. In what way is it specifically not encyclopedic? I suspect that you may well find a paper-based which does include this mnemonic, were we to hunt one down. --Matt Westwood 19:06, 9 October 2011 (UTC)

This isn't AfD. Most things in sources can't be included -- for space reasons, if no other. (Tens of thousands of pages have been written about this sieve.) So what material is included and how is a decision that must be made by the editors.

It may not be an AfD but "I don't like it" arguments are still specious. From WP:CONSENSUS: "In determining consensus, consider the quality of the arguments, the history of how they came about, the objections of those who disagree, and existing documentation in the project namespace. The quality of an argument is more important than whether it represents a minority or a majority view. The argument "I just don't like it", and its counterpart "I just like it", usually carry no weight whatsoever." --Matt Westwood 19:27, 9 October 2011 (UTC)

If you'd like to involve more editors on this earthshakingly important decision, feel free to post a neutrally-worded notice (as I did at WPM) in appropriate places.

CRGreathouse (t | c) 19:10, 9 October 2011 (UTC)

It's important to me, because that sort of stuff that interests me. It's obviously interesting enough to you that you feel the need to expend so much effort in ensuring it is removed. If you don't think it's that important, then why are you making such a fuss about it? --Matt Westwood 19:14, 9 October 2011 (UTC)

And no, plurality would NOT "suffice", WP:CONSENSUS (and common sense) is quite clear on that. WillNess (talk) 19:19, 9 October 2011 (UTC)

For the inclusion of this mnemonic to be encyclopedic information, reliable secondary sources are needed. By this I do not mean textbooks quoting the mnemonic, but reliable secondary sources discussing its cultural and/or historical significance. As far as I can tell, the material was previously sourced to two programming textbooks and c2.com, none of which provide such a source. Geometry guy 19:56, 9 October 2011 (UTC)

Huh? The inclusion of the rhyme by a widely regarded and authoritative textbook, in 1981, in archaic spelling, is clear evidence in itself of 1. its cultural significance (the inclusion itself is evidence of that) and 2. its historical significance (obviously someone wrote it long long time ago - and the origins are lost, apparently). The previous sources were weak, new source is rock solid. Clocksin and Mellish 1981 is not just another textbook, it was at the time THE textbook in its field. WillNess (talk) 20:18, 9 October 2011 (UTC)

While I've already expressed my view on it I might reconsider if it were sourced is a way that indicated its significance: someone writing about it as historic or as by a famous writer. But I've not seen that yet. Someone using archaic spelling proves nothing: I could do so if I wanted to be pointy in this reply, and many modern writers do so as a matter of course for some effect or other.--JohnBlackburne^words_deeds 20:30, 9 October 2011 (UTC)

WillNess, I'm sure you mean well, but if you want to convince other editors of your viewpoint, you need to listen to theirs. I am not asking for evidence of the cultural/historical significance of the mnemonic, I'm asking for reliable secondary sources which discuss such evidence. This is what is required for inclusion according to Wikipedia policies for verifiability and no original research. Geometry guy 20:47, 9 October 2011 (UTC)

PS. I am quite aware of the significance of Clocksin and Mellish, as I was using it in 1989, when it was already the definitive textbook on Prolog.

This is all I want to do: listen to the opinions of others, restated in the light of this new find of the new RS of C&M. That is why I asked for re-vote, especially when at least two of the supposed "opposition" specifically discuss the supposed lack of RS for it, which has now been debunked. WillNess (talk) 21:16, 9 October 2011 (UTC)

Clocksin and Mellish are not "someone". Them including it, is as clear an evidence of its significance as there could ever be. It is significant simple because it is included in that book. The comment by the Geometry guy says as much. I just don't have access to that book; it is quite probable they discuss its origins right there on p. 174. Anyone? With access to that book? Please? WillNess (talk) 21:16, 9 October 2011 (UTC)

And they didn't "write it", they used it as a book section heading. Which clearly indicates they regarded it as a widely known folklore.

Demanding sources as to its significance itself misses the point completely: We Do Not Write About Poems Describing The SoE here. We do not pick one, the best, among many others. Only in such situation would that demand be justified. No, we have here a clearly evidenced - by rock-solid RS - famous folklore rhyme, being in use for decades. What more can anyone ask? Why?? WillNess (talk) 21:23, 9 October 2011 (UTC)

I can check Clocksin and Mellish tomorrow. Please be clear about the distinction between primary source material, which only quotes the mnemonic, and secondary source material, which discusses it. Geometry guy 21:32, 9 October 2011 (UTC)

I checked it as promised. It cites the poem, attributes it to "Anon", misspells Eratosthenes as "Erastosthenes", and makes not a single further comment on the poem. So, while it is a super reliable source on Prolog, it isn't really up to much as a reliable source on the sieve or the poem. Geometry guy 21:09, 10 October 2011 (UTC)

Thanks a lot! :) We don't need it to serve as a source on the poem itself, as discussed at length below. Its inclusion in a notable 1981 textbook is all we need to establish its long-standing connection to the sieve, and attribution to Anon is proof positive of its folklore status. WillNess (talk) 13:33, 11 October 2011 (UTC)

I admire your enthusiasm. I hope you won't lose it as you continue to develop your understanding of what Wikipedia is and is trying to achieve as a free-for-all encyclopedia. Geometry guy 19:38, 11 October 2011 (UTC)

It's not just C&M either, there are other sources that cite the same jingle.

And this site: http://cplus.about.com/od/programmingchallenges/a/challenge20.htm ... cites Wikipedia itself, from before the jingle was deleted, so it has obviously been found useful enough to quote from (although I understand that WP:USEFUL don't cut no mustard here). There are plenty more, and they all use either Wikipedia or C&M as their source. I don't see the reasoning that suggests it should not appear here. --Matt Westwood 20:33, 9 October 2011 (UTC)

The relevant policy, IMO, is WP:RS (Wikipedia isn't a reliable source). CRGreathouse (t | c) 22:59, 9 October 2011 (UTC)

Retain the verse (i.e. put it back in), given the Clocksin and Mellish source is a WP:RS. -- 202.124.72.28 (talk) 23:58, 9 October 2011 (UTC)

Please log in and 'claim' your !vote. CRGreathouse (t | c) 01:45, 10 October 2011 (UTC)

Remove. The 2003 edition of Clocksin and Mellish quotes the poem, but does not discuss it. Unless other editions discuss the significance of the poem, Clocksin and Mellish are a primary source for the poem's cultural significance, not a secondary one. Ozob (talk) 00:50, 10 October 2011 (UTC)

I agree and reiterate my Remove above. If this was widely known in popular culture or by an otherwise notable author I could see making an exception but neither is the case here. My GBooks search turned up one hit and it's not even a book on number theory. Not sure why so much fuss is being made over a two line bit of doggerel; it's not even humorous.--RDBury (talk) 04:03, 10 October 2011 (UTC)

This argument does not apply because this is not a culturological article. This is not about including a poem with most cultural significance out of many, or because it had impact on general culture. This is about including one folklore rhyme in existence about SoE simply because it is folklore that has been used for decades. This is not an article about folklore rhymes about mathematical algorithms. WillNess (talk) 07:15, 10 October 2011 (UTC)

Arbitrary break

• Comment. There seem to be two clear arguments on either side of this discussion. One argument is that the rhyme appears in at least one reliable source, and therefore can be cited in the article. The other view is that, for a rhyme to be worthy of inclusion, it must have some greater significance than merely being quoted in some text. That is to say, some source must give a larger context for the rhyme. The argument seems to me like it could go either way, depending on whether the rhyme is treated as a mnemonic device as some editors have held, or as a poem as others are inclined to call it. It could be that a reasonably well-sourced mnemonic device is considered worthy for an encyclopedia to cover. Several editors have come down on either side of this question. On the other hand, I hope we can at least all agree that for a poem as such to be worthy of quotation, there should indeed be secondary sources establishing its larger context. Sławomir Biały (talk) 11:43, 10 October 2011 (UTC)

Clearly this is not a mnemonic device. That name probably isn't a proper name for it, was somehow given to it years ago and since stuck here. What it really is, is a folklore rhyme. Some say (on blogs, so can't use it) that the SoE is the only algorithm ever to get its own little poem. Regardless of that, this poem is as much an attribute of the Sieve as its alleged author, time and place of its invention, and other trivia, and should be included as part of the collection of facts about the sieve, not as a poem in its own right. Only in such a case there'd be need for its own separate RS as for its significance, context etc. But it is not here to be included as a poem in its own right, but as part of accompanying trivia.

We don't need sources as to the significance of Greece, right? It is enough to have RS establishing that Greece is indeed a birthplace of the algorithm's author; just the same it is enough to have sources establishing the text of this rhyme and its relation to the sieve (which its use as a title of a famous book's section on sieve of Eratosthenes clearly establishes).

So just as we mention the sieve's author and birthplace, it is good to mention the folklore rhyme about it. And Clocksin and Mellish is not "just some author", they are notable authors, and the book is a notable book in its field. WillNess (talk) 18:11, 10 October 2011 (UTC)

Greece is a good example. It is notable and mentioned in many reliable sources. But we don't give a paragraph (let alone a section) of the article to Greece, even though it is related to the algorithm (as its presumptive birthplace). Similarly, this folk poem has been at least quoted if not discussed in several sources, and it's similarly not clear whether we should devote space to it in this article. I and others feel that we should not. CRGreathouse (t | c) 19:19, 10 October 2011 (UTC)

Greece is not a good example, because there are a lot more aspects to Greece than its relationship to SoE. On the other hand, this rhyme relates only to the SoE. So your argument looks like a straw man to me. I and others feel that we should devote space to it in this article. I can set up good straw men myself - here's one: Prime numbers are discussed in several sources, so should we remove all reference to them here? --Matt Westwood 20:46, 10 October 2011 (UTC)

Worse than a strawman, you (CRGh) shift the point of reference in your reply. The question was, whether we need sources as to the significance of Greece, or the rhyme. Answer to both: we don't. As to the inclusion, just as we mention Greece as part of a trivia on the subject, so we should the rhyme. "Greece" is self-descriptive so we can get away with just naming it; the rhyme's short text will serve is its description. Surely it does not deserve its own article, like Greece does. WillNess (talk) 13:23, 11 October 2011 (UTC)

• Thanks WillNess for explaining. But at this point, I don't see any particularly compelling reason for the poem to stay. (Although I'm still neutral on the matter of whether it should be included.) It's not clear to me what information we wish to convey by its inclusion. Is it an idle bit of trivia, then? If so, maybe there is a way to incorporate it in the article that is less obtrusive. For instance, it could do in place of an image in the section that describes the algorithm. Sławomir Biały (talk) 22:51, 10 October 2011 (UTC)

(apologies for being verbose but I do as well as I can). That illustration is a valuable visualization aid. The rhyme adds much liveliness to the article, makes it less a dry maths. The point is, this is not a mathematical article in a peer-reviewed math journal. You come from the point of view of a mathematician, but the target audience is not. This subject matter is not at all an advanced math. It is very well accessible to children, laypersons and programmers :), and having pictures and rhymes adds greatly to the overall tone and accessibility, as well as references into more mathematical stuff, for further exploration. That is why I consider a minimalistic approach to be wrong here. WillNess (talk) 13:23, 11 October 2011 (UTC)

That's most clarifying, thanks. The point that including things like this reduces the dryness of the article and makes it more appealing to a wider readership is well-taken. I've tried this compromise solution. While the poem isn't part of the main text, it does provide a bit of color to an otherwise dull section of the article. I'm curious to know what other editors think. Sławomir Biały (talk) 13:52, 11 October 2011 (UTC)

I agree that it's a compromise, in the sense that I find the article better without that addition but the addition better than the version in which the poem gets its own section. CRGreathouse (t | c) 16:43, 11 October 2011 (UTC)

This is superb! Thanks a lot! WillNess (talk) 16:46, 11 October 2011 (UTC)

Thx guys. I'd all but given up on this! I'm more than happy. The compromise solution is IMO better than how it was originally presented. --Matt Westwood 17:34, 11 October 2011 (UTC)

Yes it certainly is much better that way than it was before. This is what I'd hazard to call a constructive criticism and a constructive change. WillNess (talk) 18:43, 11 October 2011 (UTC)

Yes, I also think that the quotebox is a nice solution, using our editorial freedom to decorate articles with suitably chosen images and related media. Geometry guy 19:38, 11 October 2011 (UTC)

Folklore mnemonic, not Folklore Mnemonic.
Must I remind people of the obvious fact that it is incorrect to capitalize the initial m in mnemonic in this setting? WP:MOS clearly forbids capitalizing an initial letter merely because it is in a section heading, and that's what you see throughout Wikipedia. Michael Hardy (talk) 04:21, 10 October 2011 (UTC)

Arithmetic progressions

I added a stub section on using the sieve in arithmetic progressions. This is very common in practice, so I thought some material was warrented. The paper I cited was the earliest I found, and seems to be the paper originating the technique (at least that's the impression the author gives). It's hard to imagine it's that recent, though -- has this really only been around a hundred years?

More material would be welcome.

CRGreathouse (t | c) 18:44, 6 October 2011 (UTC)

Feel free to add some. No, feel obliged to add some, because as it is written now - by you - the subsection conveys exactly 1 bit of information. Guidelines are clear on that, readers should not be made to chase links and even moreso references to find out what the heck is this one sentence talking about. "May be used"... how? In what way? Whatever for? And myriad other unanswered questions. You seem to think every WP reader has to have free access to academic sources, and those without access, well to heck with them, right, let them pay admission and tuition and whatever, or else let them be left in the dark, right? Is that the thinking behind your minimalist approach? WillNess (talk) 11:55, 9 October 2011 (UTC)

I am absolutely not obligated to do what you require of me. CRGreathouse (t | c) 18:31, 9 October 2011 (UTC)

I just expected you'd want to improve an incomprehensible subsection. You seem to claim there's no obligation on your part to improve an otherwise incomprehensible passage that you yourself added. That's not what I'd expect. Hmm. WillNess (talk) 18:45, 9 October 2011 (UTC)

It's not incomprehensible, it's a stub. I would like to improve number-theoretical stubs in Wikipedia. But I'm certainly not obligated to do so!

CRGreathouse (t | c) 18:57, 9 October 2011 (UTC)

Example changes reverted

I've reverted the changes made to Example as it gave misleading impression of the algorithm removing the composites. It is THE defining characteristic of the basic SoE that it does not remove, but marks in the same sequence the composites so the direct addressability isn't broken and they're later removed all at once. WillNess (talk) 06:47, 22 October 2011 (UTC)

I've made a sandbox edit of this example with non-diluted intermediary sequences shown. If that's preferable to what's already in the article, please voice your opinions. I personally think it has too much detail. WillNess (talk) 07:13, 22 October 2011 (UTC)

Image

The new image recently changed on the page can only be unambiguously seen as a rendition of Euler's sieve, not the sieve of E. There was a lengthy discussion on the matter on this page once, IIRC, ending in the decision for the image that was just now replaced. So which is better? Should the previous one be restored? WillNess (talk) 07:01, 31 October 2011 (UTC)

I added it, seeing it on Prime number and thinking it better because of its size (the previous one is too wide) and its quality (it's a FP, while the previous one has a number of rendering issues). I was not aware of any previous discussion, but I don't agree that the current image can only be seen as a rendition of Euler's sieve: it is like the example, where once struck out a number cannot be struck out again. Yes the numbers could be recoloured but that is as unnecessary as striking out numbers in the example multiple times. And even if it better represents Euler's sieve then that is, according to the article, a version of the sieve of Eratosthenes.

Looking at the file history though it seems it did once work like the previous version. In fact that was the version promoted to featured picture, before being changed without discussion of any sort. Given that and the disagreements the current version has generated I've been bold and reverted it.--JohnBlackburne^words_deeds 14:53, 31 October 2011 (UTC)

Thank you. I think this way it is closer to the basic variant and thus has less potential for confusion. WillNess (talk) 20:01, 31 October 2011 (UTC)

NB! The image has been re-reverted to the wrong version. If you know how to restore it to its previous, correct version - that is the very first version by Brian0918 or the restored one by JohnBlackburne - please do restore it. For some reason I can't find the way to do that myself. -- WillNess (talk) 16:24, 22 November 2011 (UTC)

nevermind, did it myself. WillNess (talk) 16:35, 22 November 2011 (UTC)

Pseudocode

I noticed that when the pseudocode was recently updated (citing Sedgewick) the loop was changed to run up to n/2 rather than sqrt(n). Was this intentional?

I was not able to find anything on the SoE on that page when I looked at the Amazon preview, so I can't tell if the book actually uses this bad variant.

CRGreathouse (t | c) 16:52, 25 October 2011 (UTC)

Page 16, 1992 edition, just as it says in the citation. Chapter 3, "Elementary Data Structures", subchapter on "Arrays". Didn't want to add any OR on top of the elementary derivation needed to get to the pseudocode from the actual code in the book. Why do you think this is a "bad variant" as opposed to just "non-optimized variant"? Does this change the algorithmic complexity of the code? Will add ISBN there shortly. WillNess (talk) 15:14, 26 October 2011 (UTC)

Let's see... by Mertens' second theorem it increases the time requirement by n log 2 in the RAM model, so the big-O complexity is unchanged compared to other non-optimized versions. But it's actually pretty significant in reality since the extra work is cache-incoherent. CRGreathouse (t | c) 17:58, 26 October 2011 (UTC)

I've seen it stated several times (in blogs, and on RosettaCode), that changing {A[j] = false} into {if A[j] is true: A[j] = false} makes it run faster precisely because of cache-issues. That's how it was in this article too, before the big changes. Maybe with that tweak the n/2 wouldn't matter so much, cache-wise, and we could stick with this bare minimum, basic version. We do mention the "refinement" of stopping at the square root, in the "Algorithm description" section. WillNess (talk) 07:48, 27 October 2011 (UTC)

That tweak is quite small compared to testing only up to the square root. CRGreathouse (t | c) 15:06, 27 October 2011 (UTC)

Here's a short and sweet coding technique for calculating prime numbers I wrote in C#:

static List<int> m_primes = new List<int>(100);

static void Main(string[] args) {

   for(int num = 2; num < 120; num++)
   {
       bool isPrime = true;
       foreach(int prime_num in m_primes)
       {
           if(num % prime_num == 0)
           {
               isPrime = false;
               break;
           }
       }
       if(isPrime) m_primes.Add(num);
   }

   foreach(int prime_num in m_primes)
       Console.Write(prime_num + "\t");

} 214.26.214.163 (talk) 17:00, 6 February 2013 (UTC) Slayemin

Recent changes

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)

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)

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)

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)

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)

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)

(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)

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)

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)

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)

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

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)

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)

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)

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

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

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)

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)

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)

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)

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)

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)

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)

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)

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)

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. It does so by iteratively marking as composite the multiples of each prime number, starting with the multiples of 2.

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. 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.

It is one of the most efficient ways to find all of the smaller primes (below 10 million or so). 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.

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

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)

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. It does so by iteratively marking as composite the multiples of each prime number, starting with the multiples of 2.

It is one of the most efficient ways to find all of the smaller primes (below 10 million or so). 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.

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. 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.

(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)

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)

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)

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)

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

---

---

Erathotene?

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)

Animation is distracting : continuously looping feature

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)

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)

Sieve of Eratosthenes animation

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)

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)

Bit Complexity

Where exactly is the reference to the bit complexity being $O(n(\log n)(\log \log n))$ ? I checked the journal and I was unable to find where this was stated.

I was unable to find anything online, yet I calculated it to be $O(2^{n}log(log(2^{n})))$ Bekamancer (talk) 01:08, 7 March 2015 (UTC)

@Bekamancer: Sieve of Eratosthenes#Algorithm complexity says "calculating all primes below n" and not n-bit primes so your 2ⁿ is certainly not needed. Then you are just missing a log n factor which probably comes from numbers below n having O(log n) bits. I haven't read the reference. PrimeHunter (talk) 01:31, 7 March 2015 (UTC)