Sieve of Eratosthenes

Reason

Ran across this at WP:RD/C. I was impressed- not necessarily by the algorithm but how necessary the image was to the article for it to make any sense at all. This is the very definition of encyclopedic for me.. so that's why it's nom'd. Preemptively answering an objection (this puzzled me too), it only starts looking for multiples of the prime at that prime squared and stops counting multiples once you've found all primes from 1 to the square root of your upper bound. Also the animation isn't as slow as it seems, let it load.

Proposed caption

A tabular method for determining primes.

Articles this image appears in

Sieve of Eratosthenes

Creator

de:Benutzer:SKopp

• Support as nominator froth^t 22:20, 24 September 2007 (UTC)[reply]
  • Make that a Support edit 1 --froth^t 18:33, 25 September 2007 (UTC)[reply]
• Oppose because (a) it makes sense to place the first few numbers slowly, and then the rest more quickly for series of multiples of each prime, and (b) it's inconsistent - sometimes previously labelled multiples are coloured in, and sometimes they aren't. The inconsistency is a real deal-breaker. Please fix it and upload again. Thank you. Separa 22:38, 24 September 2007 (UTC)[reply]
  • I think, if you look at it, this is because of what Froth already identified - "it only starts looking for multiples of the prime at that prime squared". After this, I think, it always relabels previously-labelled multiples. TSP 22:41, 24 September 2007 (UTC)[reply]
• Comments: Good principle. A few issues with it:

(a) it takes an awfully long time to fill in the multiples of 2 - I almost got too bored to finish watching it. Could be speeded up? It only needs to take a second or two doing this, I think, followed by perhaps a second pause before starting the next number.

(b) I'd like it to be clearer when it is marking a prime, and when it is marking excluded numbers - I got confused when it started colouring in lots of numbers in purple. Perhaps it could circle primes, or cross out known non-primes, and keep colouring in the box for the other purpose. TSP 22:41, 24 September 2007 (UTC)[reply]

Agreed. Needs to be much faster after the first couple of multiples. Also, the fact that it starts at the multiple squared is confusing and not self-explanatory...yet. Stevage 02:49, 25 September 2007 (UTC)[reply]

• Comment (abstain): I agree with the above. The inconsistency must be fixed, and it must be sped up. Indicate 2, then indicate 2x in one fell swoop. Give us a moment to see what you did, then move on. This has great potential, but is unacceptable in its current form.--HereToHelp 23:48, 24 September 2007 (UTC)[reply]
  • Are you sure about the inconsistency? Is it not just that, as the nominator (and the relevant WP page) says, "it only starts looking for multiples of the prime at that prime squared"? TSP 23:54, 24 September 2007 (UTC)[reply]
    • Better, but I still think it's confusing to have 3 start at 9 (rather than 6) and 5 at 25 (rather than 10). I also think that it would be better to show them all at once, rather than show each multiple of 2 (60 of them!) individually.--HereToHelp 23:36, 25 September 2007 (UTC)[reply]
• Support Used this method before, but never really understood it until now. Great nom. Debivort 02:44, 25 September 2007 (UTC)[reply]
• Oppose, image is huge, 2MB for something that shouldn't need nearly that much. It wouldn't be slow to load if it was properly optimized. Night Gyr (talk/Oy) 04:24, 25 September 2007 (UTC)[reply]
  • Upon doublechecking, the thumbnailing algorithm has multiplied the filesize 10x. The animation still seems a bit slower than it ought to be. Night Gyr (talk/Oy) 04:26, 25 September 2007 (UTC)[reply]
    • The tiny thumbnail is massive, but check out the article's thumbnail. I think it's fullsize- and the file size is tiny as expected. We just have to make sure that it's never thumbnailed too small --froth^t 18:24, 25 September 2007 (UTC)[reply]
• Oppose Too slow. --Janke | Talk 06:29, 25 September 2007 (UTC)[reply]
• Strong oppose; you'll need to speed up that animation by a lot if you don't want laymen (like myself) to fall asleep before the animation finishes or play Minesweeper waiting for the image to load. -- Altiris Helios Exeunt 09:26, 25 September 2007 (UTC)[reply]
• Support edit 1. I've modified the timing to speed up the unimportant frames while giving the important frames more attention. It's down from about 1:41 to 0:35 in length. — BRIAN0918 • 2007-09-25 14:20Z
  • I think this is a sufficiently big improvement to go immediately onto the page, as most people here seem to have found the speed a problem. I'd still, if being fussy, like (a) a pause between filling in the multiples of one prime, and filling in the next (at the moment, your eye is drawn to the bottom by the multiples, then you almost miss the next prime going in); and (b) a clearer distinction between how primes and non-primes are marked (but that would probably require a complete remake of the image). TSP 14:35, 25 September 2007 (UTC)[reply]

I was going to make the same two comments. Perhaps the primes could be marked with a circle around the number or something instead of just yet another colour. Also, perhaps all the filled in squares could be faded out at that point. Come to think of it, it would be even much clearer if all the multiples were marked by an X over the number, indicating clearly that these numbers were rejected. Stevage 03:12, 26 September 2007 (UTC)[reply]

• • Took it out of the thumb so people dont have to download a 2M image to see it :) --froth^t 18:33, 25 September 2007 (UTC)[reply]
• I like edit 1. To the haters, there's no inconsistency at all.. check out the article on the sieve and it gives a description of the algorithm. It's unnecessary to check for multiples of the prime before the prime squared because they're always already colored in. Also it only needs to run through the square root of the upper bound (100). In this case it stops at 7 since 8, 9, and 10 are already shaded. And where are you getting your 2M figure? It's only about 150-200k. Very tiny compared to a lot of FPs --froth^t 18:22, 25 September 2007 (UTC)[reply]
  • Oh you were talking about the thumbnail. See my reply to night gyr's comment above --froth^t 18:33, 25 September 2007 (UTC)[reply]
• Support Edit 1. A good Wikipedian-created image that does what it says on the tin. I still think that a few improvements could be made, per my comments above, but that's really quibbling - this is still a good image. TSP 19:14, 25 September 2007 (UTC)[reply]
• Comment It's a good animation and I like it (no support because I'm not familiar with the guidelines here). The faster version is better. Regarding the "inconsistency" that when crossing off multiples of three it does not cross of six: I do think it's rather confusing. I also think it's not essential to the algorithm to start crossing off at the square of the prime number. It does speed up the algorithm a bit, but only a little bit. So I think that for educational reasons it would be better to scrap that rule and cross off multiples of every prime starting from the prime number itself. -- Jitse Niesen (talk) 01:52, 26 September 2007 (UTC)[reply]
• My vote has been changed to Support Edit 1 by brian0918; the common layman won't fall asleep now! Cheers, and may this nomination be promoted. -- Altiris Helios Exeunt 02:36, 26 September 2007 (UTC)[reply]
• Support edit. Very helpful and well-implemented.--ragesoss 03:11, 26 September 2007 (UTC)[reply]
• Comment: Better now, speeded up, but it still lacks something. As said, X-ing out would be much better than the almost same colors as the primes. --Janke | Talk 06:01, 26 September 2007 (UTC)[reply]
• Support Edit 1. A nice implementation made much friendlier by the edit--Saxobob 09:13, 26 September 2007 (UTC)[reply]
• Oppose. The time length isn't the deciding factor for me. The coloring is inconsistent. All multiples of 5 are colored blue, even the ones that were previously colored red, apart from 15 and 20. Why? They should all be treated the same. - Mgm|^(talk) 10:28, 26 September 2007 (UTC)[reply]
  • -_- this has been answered several times. It's part of the algorithm that you start from the prime SQUARED- since 15 and 20 are less than 25 they're skipped over. You're guaranteed that every multiple of the prime from the prime to it squared will have already been crossed off- that's why you just start at the square --froth^t 10:57, 26 September 2007 (UTC)[reply]
  • Your oppose reason is not valid. Please supply another oppose rationale or change your vote. — BRIAN0918 • 2007-09-27 19:12Z
• Comment: Since you stop testing at the square root of the largest number to test, why not organize your numbers in a square to represent that fact? 10x10 -> largest number 100 or 11x11 -> largest number 121.Wwcsig 13:24, 26 September 2007 (UTC)[reply]
• Comment Why use so many different colors at all? It's confusing. Why not use a single color (say, a shade of red) for the first "2", then a different color (say, a shade of blue) for multiples of 2. Then use the same shade of red for the first "3" (they're both primes, so they get the same color), and the same shade of blue for multiples of 3. This eliminates the confusion that's caused by composites being colored one color, then another. Once the seive is completed, use a different shade of red to show the primes that the sieve finds. Spikebrennan 18:36, 28 September 2007 (UTC)[reply]
• Oppose – To a non-mathematician the algorithm is non-obvious and the colouring is utterly confusing. Just use three colours, one for the number used is the current step of the sieve, one for non-primes and then one for primes. And highlight clearly you start fron n² when using n in the sieve by making the number flash or something. Centy – reply• contribs – 22:02, 28 September 2007 (UTC)[reply]
• Oppose per centy. But if those issues are adressed, I'll change my !vote immediately. The image in itself is very encyclopedic, but the image can still be improved. – sgeureka ^t•c 23:14, 28 September 2007 (UTC)[reply]
• Oppose: It's neither eye catching nor does it add that much to the article to warrant FP status. Simply looking at it a hundred times you probably won't get what's going on (I wouldn't have anyway), without reading the article, in turn for which you don't really need the picture. --snowolfD4 ^{( talk / @ )} 14:14, 2 October 2007 (UTC)[reply]
• Support Edit 1 To translate, after 2,3,5 and 7 every number that isn't divisible by 2,3,5 or 7 is a prime. Hooray for math! Calibas 01:33, 3 October 2007 (UTC)[reply]

Calibas, you know that is not true.Cuddlyable3 09:09, 20 October 2007 (UTC)[reply]

Promoted Image:Animation Sieve of Eratosth-2.gif MER-C 03:58, 3 October 2007 (UTC)[reply]

Post-promotion discussion

There is one side where this image could be improved: it could give an explanation on the "inconsistencies" (a text on the side explaining that it starts crossing at prime squared) and why it stops "prematurely" (a text on the side explaining that since the current prime is greater than the root of 120 it'd stop now). I'd have done this myself, if I weren't in a tight deadline for school work.

I agree that just 3 colours would work best here: one for numbers not crossed out (e.g. blue), one for numbers crossed out in previous phases (e.g. grey), one for numbers crossed out in the current phase (e.g. red). At the end of each phase the red would change to grey. The dimensions of the rectangle don't matter too much — but I personally think it would be handy to have it be 12 squares wide, so that the pattern for the introductory small multiples is more obvious. As for starting at 2p versus p², I think as long as we're showing things being crossed out multiple times, it makes more sense to start at 2p (this variation doesn't affect the asymptotic performance of the algorithm anyway). Dcoetzee 20:05, 26 May 2008 (UTC)[reply]

I uploaded a non-overlapping version over this image before looking here, I didn't think there was a reason for the inconsistencies on the image. (I had only read File talk:Animation Sieve of Eratosth-2.gif, where nearly everyone seemed to agree that it needed a change). If it's an important feature of the old version, feel free to revert the revision. -- 6Sixx (talk) 07:10, 5 March 2009 (UTC)[reply]

reverted. The changed version spawned more than one dispute at Talk:Sieve of Eratosthenes and more generally a FP should not be radically changed without previous discussion. And this really is the wrong place to discuss this: any further discussion should take place at the above article talk page or some other appropriate venue.--JohnBlackburne^words_deeds 02:14, 1 November 2011 (UTC)[reply]