Talk:Sieve of Eratosthenes

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)

Benchmark

As I remember, the Sieve of Eratosthenes was a popular benchmark for early microcomputers. I thought I might find that discussed here. (Well, possibly.) It seems not to be. I wanted to reference it from the MIPS page. Gah4 (talk) 09:02, 13 August 2016 (UTC)

It was commonly used as a benchmark. Bubba73 ^{You talkin' to me?} 15:57, 13 August 2016 (UTC)

Visual layout

While improving greatly on various aspects of typographic style (thank you for that!), 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)

(Undo good faith edit that doesn't belong in this subsection. Complexity is already discussed elsewhere in the article. Passing mention of another incremental algo is enough, no need for _its_ deep analysis.)

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)

Animation inconsistent : Does not mark 6 in green when marking multiples of 3

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)

Add or remove link to sieve theory

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, @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 generalizations of the sieve of Eratosthenes is quite the correct turn of phrase (the word 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

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

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)

Correction in Segmented Sieve

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 $\Delta \geq {\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)

The tables in Computational analysis and Algorithmic complexity make no sense

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)

Naming of linear sieve as "Euler sieve"

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)

Missed optimization in animation and pseudo code

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 √n do
        if A[i / 2] is true
            for j = i2, i2+2i, i2+4i, i2+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)