Talk:Sieve of Eratosthenes#Symbolic formulas: a recap

While improving greatly on various aspects of typographic style (thank you for that!), [https://en.wikipedia.org/w/index.php?title=Sieve_of_Eratosthenes&diff=next&oldid=757647493 a recent edit by an IP user 81.129.155.32] also destroyed the carefully created visual layout of pseudocode snippets and examples throughout the whole article.

Please don't do that without discussing it here and reaching a consensus first. Thanks. WillNess (talk) 10:12, 24 January 2017 (UTC)

A recent revert has the above as its edit summary. While this might be true, it is discouraging to new editors. Too many of those, and someone will stop trying. Is it possible to put somewhere else in the article? Or change such that it does make a useful addition? It looks like someone who really does understand the subject, not a random, inappropriate, edit. Gah4 (talk) 20:44, 6 April 2017 (UTC)

When the animation marks multiples of 3 in green, it doesn't mark the number 6 in green. You could argue this is because 6 is already marked red as a multiple of 2. But the animation then marks other multiples of 3 in green even when they have already been marked in red as a multiple of 2 (e.g. 18, 48, 54, 96). It feels like the animation should mark 6 in green when marking multiples of 3. — Preceding unsigned comment added by 62.190.148.115 (talk) 18:24, 18 September 2017 (UTC)

:The caption says "including optimization of starting from prime's square". That means the multiples of 2 are marked from 2² = 4 (which makes no difference), multiples of 3 are marked starting from 3² = 9, multiples of 5 are marked from 5² = 25, and multiples of 7 from 7² = 49. Multiples below the square have always been marked by a smaller factor. Clicking the image leads to :File:Sieve of Eratosthenes animation.gif which also explains it. PrimeHunter (talk) 18:46, 18 September 2017 (UTC)

::You probably meant "Multiples below the square have already been marked by a smaller factor." Just pointing this out for the benefit of future readers here. WillNess (talk) 17:51, 29 April 2018 (UTC)

A couple of days ago I made a simple edit to remove a link from the headline, which is generally considered bad form. In order to keep all the information intact, I added the link to the end of the sentence instead of inside the headline.

This change was RVed by David Eppstein, who stated "Sieve theory is much more advanced, is not needed to explain this sieve". So apparently he thinks we should not have this link in this article. However, the RV re-added a link to that article.

Following David's lead, I then removed the link, fixing both problems at once. Then WillNess RVed that, stating "undo per the reasons for the previous revert", thereby doing precisely the opposite of what that revert actually claimed to do.

In any event, as it seems people want to edit war over this, {{ping|David Eppstein}}, should there be a link to sieve theory in this article or not? Maury Markowitz (talk) 11:47, 19 March 2019 (UTC)

: Hi, I'm sorry, I should have paid more attention, I thought you reverted back to your previous version. Turns out you just removed the link from the lead. I think probably it should be there, still, as it gives the reader more to explore. If some policy prevents us from this, that's just too bad. But the phrasing in your first edit was too heavy for the lead. WillNess (talk) 12:12, 19 March 2019 (UTC)

::If it's not appropriate for the lede, and it's not, remove it. Linking out of the title is bad form in any case. Maury Markowitz (talk) 14:10, 19 March 2019 (UTC)

:::I think sieve theory should only be mentioned in the lead if that mention serves to summarize some substantive part of the body, per MOS:INTRO. Just throwing it into the lead without having anything about sieve theory in the article body does not serve any explanatory purpose, and serves to make the lead more WP:TECHNICAL when we should be striving to make it less so. It should definitely not be linked when we first use in bold the phrase "sieve of Eratosthenes" (as Maury left it) as that violates MOS:BOLDAVOID, and I think working it in elsewhere in the lead could be awkward. And Maury's earlier attempt at working it in, tacking "using an application of sieve theory" at the end of one of the sentences, not only makes the sentence longer and harder to understand, but creates the false impression that sieve theory came first and this particular sieve was one of its applications. In fact, this sieve was known long long before, and sieve theory was named after it. —David Eppstein (talk) 16:04, 19 March 2019 (UTC)

:::: My two cents: the original version (that was changed by Maury Markowitz) was terrible (for the reasons articulated by multiple people above) and removing the link was good. The current version seems fine; and maybe everyone in this discussion is happy with it? If anyone does want to, it seems to me that the right place to add a link to "sieve theory" would be in the last paragraph of the lead, which currently reads

::::

One of a number of prime number sieves, it is one of the most efficient ways to find all of the smaller primes. It may be used to find primes in arithmetic progressions.

:::: (cites omitted). For example, here is one possible way to do it:

::::

One of a number of prime number sieves, it is one of the most efficient ways to find all of the smaller primes. It may be used to find primes in arithmetic progressions. The study generalizations of the sieve of Eratosthenes is called sieve theory.

:::: But it would also make a perfectly good member of a See Also section. --JBL (talk) 16:17, 19 March 2019 (UTC)

::::: I'm not sure that {{tq|generalizations of the sieve of Eratosthenes}} is quite the correct turn of phrase (the word {{tq|generalizations}} feels a little off in this context), but a sentence in that vein seems like a good idea to me. XOR'easter (talk) 16:36, 19 March 2019 (UTC)

:::::: I agree with David that the link to sieve theory is misplaced in the first sentence. I agree also that the link to sieve theory must appear at the end of the lead. It must be there for giving context, but also because the article present some variants that are sieves but not exactly Erastothenes' one. So, I suggest to replace the last paragraph of the lead by

:::::::{{tq|The Sieve of Eratosthenes is the oldest and the simplest of a family of algorithms, which proceed similarly and are therefore called sieves. Some, the prime number sieves, are used for fast computation of small primes. Other sieves are used for generating other subsets of the natural numbers, and for estimating the number of their elements up to a given bound.}}

:::::: By the way, the capitalization of "Sieve" after the article seems strange to me. IMO, either the article should be removed, or "sieve" should be uncapitalized. This is a question for native English speakers. D.Lazard (talk) 17:34, 19 March 2019 (UTC)

::::::: I much prefer the current lead untouched, and the link just added to the See Also section. Keep the lead simple, for general accessibility. Any technical detail can be added somewhere down in the body, if necessary. WillNess (talk) 08:07, 20 March 2019 (UTC)

:::::::: OTOH the last sentence of the lead does feel too short, so maybe indeed augment it as

::::::::: {{tq|One of a number of prime number sieves, it is one of the most efficient ways to find all of the smaller primes. It may be used to find primes in arithmetic progressions. (here's the addition:) The study of general techniques in number theory similar to the Sieve is known as the sieve theory.}}

:::::::: Something like that. WillNess (talk) 08:19, 20 March 2019 (UTC)

Hi,

It says in the segmented sieve section that the segment size delta should be chosen less than or equal to sqrt(n). The issue is that then the sieve doesn't find prime factors between delta and sqrt(n) in later segments. Shouldn't it be greater than sqrt(n) instead? — Preceding unsigned comment added by Ovinus Real (talk • contribs) 06:29, 13 July 2020 (UTC)

:If $\backslash Delta\backslash ge\; \backslash sqrt\; n,$ all primes whose multiples must be considered belong to the first segment. Otherwise, primes in other segments must be included in "found so far". I have edited the article for clarifying this. D.Lazard (talk) 10:02, 13 July 2020 (UTC)

It is unclear what the tables are trying to show in Computational analysis and Algorithmic Complexity. "following is a table showing the actually measured number of operations for a practical implementation of the sieve of Eratosthenes as compared to the number of operations predicted from the above expression" so it doesn't even show the implementation? How exactly is wheel factorization used to optimize the sieve?

--Abstractsail (talk) 07:08, 3 September 2020 (UTC)

I skimmed the given reference http://research.cs.wisc.edu/techreports/1990/TR909.pdf and it don't see any mention of Euler. Anyhow clearly Euler used the techniques for proofs and not as a computer algorithm to generate primes in linear time (I don't think time complexity was ever his concern in a math proof). So I don't know where the name actually comes from. Wqwt (talk) 20:27, 29 October 2021 (UTC)

: this used to be called someth like "the version of sieve in Euler's proof of zeta function", and then some editor just shortened it. There was much discussion of this version in haskell-cafe around 2010 where that short name was explicitly used, if that counts for anything. (apologies for the typos, if any) -- WillNess (talk)

(and the date is: ) WillNess (talk) 15:14, 28 May 2022 (UTC)

Turns out I misremembered this thing entirely, sorry for that. It was introduced as such right away. Here's the first version of the article where that section appeared: https://en.m.wikipedia.org/w/index.php?title=Sieve_of_Eratosthenes&oldid=282870717 -- WillNess (talk) 15:25, 28 May 2022 (UTC)

:This line is indeed edited many times since it was originally introduced in the version linked from 2009. However although the version from 2009 introduces the claim that the linear sieve is based on a proof idea from Euler, it does not include the currently referenced work of Sorenson as a source yet. This was added (by you) 4 years later in 2013 https://en.wikipedia.org/w/index.php?title=Sieve_of_Eratosthenes&diff=prev&oldid=584496363.

:Could you clarify why this was added as a source (maybe it was by mistake?), because I also could not find anything in Sorenson's article attributing the linear sieve to Euler. Fireline11 (talk) 10:42, 31 May 2025 (UTC)

Both the animation and pseudo code mention that they include optimization (starting from prime squares). The argument there being all number smaller than prime squared have already been marked. It then goes and marks prime^2, prime^2 + prime, prime^2 + 2 * prime, ... but half of those numbers are even. Another common optimization is therefore to mark only prime^2, prime^2 + 2 * prime, prime^2 + 4 * prime, ... for any prime > 2. Taking this one step further is to exclude all even numbers from the array of booleans in the first place:

algorithm Sieve of Eratosthenes is

input: an integer n > 1.

output: all prime numbers from 2 through n.

let A be an array of Boolean values, indexed by integers 1 to n / 2,

initially all set to true.

for i = 3, 5, 7, 9, ..., not exceeding {{math|{{sqrt|n}}}} do

if A[i / 2] is true

for j = i², i²+2i, i²+4i, i²+6i, ..., not exceeding n do

A[j / 2] := false

return all i <= n such that i == 2 or i is odd and A[i / 2] is true.

Apart from saving the time to mark all even numbers it also saves half the memory and is therefore a common optimization too.

: yes this is mentioned in the article. But we also must keep it simple. So it's a balancing act. -- WillNess (talk)

(here's the sig with the date, IIRC how to do it) WillNess (talk) 15:13, 28 May 2022 (UTC)

:That's a good optimization. You can just mention sieving by skipping evens. Further simple optimizations are mentioned at https://cp-algorithms.com/algebra/sieve-of-eratosthenes.html#sieving-by-the-odd-numbers-only Wqwt (talk) 05:10, 25 August 2022 (UTC)

::it is mentioned, in Overview. WillNess (talk) 14:52, 3 October 2022 (UTC)

Are we married to mentioning Sorenson's work? Maybe we should say something else along the lines of '...the space-saving sieve as attributed to Dunten, Jones and Sorenson...'. The citation is also broken, but this one is not; https://doi.org/10.1016/0020-0190(96)00099-3.

I'm not even sure that is the correct author/paper the contributor was referring to, but there appears to be nothing commonly referred to as the Sieve of Sorensen. 69.162.230.42 (talk) 00:34, 15 August 2024 (UTC)

:I found a not-so-broken link to the same paper. I updated the text to refer to the actual name of the Sieve from the paper, but also left an attribution to J. Sorenson, this maintains an attribution with a more correct name. I also updated the citation to a living-link. I think until the Pseudosquares Prime Sieve is commonly referred to as the Sorenson Sieve we should refrain from forcing a name.

:I kind of wonder if a student of his added this while reviewing material. 69.162.230.42 (talk) 00:52, 15 August 2024 (UTC)

The section on the segmented version gives the following motivation in the second sentence.

"For large n, the range of primes may not fit in memory; worse, even for moderate n, its cache use is highly suboptimal. The algorithm walks through the entire array A, exhibiting almost no locality of reference."

I think this sentence is worded too strongly. Locality of reference of the pseudocode given in the section above is actually not terrible and memory accesses are very regular. Therefore, I propose we rewrite it to

"For large n, the range to be sieved may not fit in memory and even for moderate n, its cache use is not optimal."

This way we refrain from justifying the segmented sieve (which is a more niche topic) by making strong statements about problems with the basic implementation, but we touch on the two main things it helps with.

1. Sieving up to a higher limit N

2. Better usage of CPU caches.

Happy to discuss if there is disagreement. I saw there was already quite a lot of discussion on the segmented sieves so I do not want to step on anyone's toes here. Fireline11 (talk) 12:06, 31 May 2025 (UTC)