# Sieve of Eratosthenes **URL:** \ **Category:** Factual Questions\ **Created:** [December 11, 2013, 7:21pm UTC](https://boards.straightdope.com/t/sieve-of-eratosthenes/676097 "2013-12-11T19:21:42Z")\ **Posts on this page:** 20\ **Page:** 2
**Author:** ![pulykamell](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/pulykamell/32/3166_2.png) [@pulykamell](https://boards.straightdope.com/u/pulykamell)\ **Post date:** [December 11, 2013, 10:06pm UTC](https://boards.straightdope.com/t/sieve-of-eratosthenes/676097/21 "2013-12-11T22:06:12Z")
> [@Canadjun](#): > > And if he is using the Sieve of Eratosthenes to determine if 54,898,390,234,005,943,587,727,239,987,774,321,490,934,981 is prime then when he (eventually) has determined its primality he has also determined the primality of all numbers less than it. As **Chronos** said, the point of the Sieve is to generate **all** primes up to a given number. Sure. I understand that. But I think the OP is saying that it kind of follows from the definition, and is wondering why it’s so special to get a name. Yes, there is an extra step there, but it seems to be self-evident from the definition. I’ve wondered about this myself. ---
**Author:** ![whc.03grady](https://avatars.discourse-cdn.com/v4/letter/w/a6a055/32.png) [@whc.03grady](https://boards.straightdope.com/u/whc.03grady)\ **Post date:** [December 11, 2013, 10:17pm UTC](https://boards.straightdope.com/t/sieve-of-eratosthenes/676097/22 "2013-12-11T22:17:21Z")
> [@pulykamell](#): > > I’m not sure he meant “by looking” in the sense of “just looking at it” but rather by, well, scanning to see if there are any integral divisors between 1 and, well, I guess the square root of the number. Yes, thank you, that is what I meant. “Looking” as in “checking”, which, I guess, constitutes applying an algorithm. > [@pulykamell](#): > > But I think the OP is saying that it kind of follows from the definition, and is wondering why it’s so special to get a name. Yes, there is an extra step there, but it seems to be self-evident from the definition. I’ve wondered about this myself. Exactly. ---
**Author:** ![DrCube](https://avatars.discourse-cdn.com/v4/letter/d/a3d4f5/32.png) [@DrCube](https://boards.straightdope.com/u/DrCube)\ **Post date:** [December 11, 2013, 10:20pm UTC](https://boards.straightdope.com/t/sieve-of-eratosthenes/676097/23 "2013-12-11T22:20:53Z")
A lot of things look simple in hindsight. The genius ideas even more so. Look how long it took to come up with the number zero. Or sliced bread. ---
**Author:** ![pulykamell](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/pulykamell/32/3166_2.png) [@pulykamell](https://boards.straightdope.com/u/pulykamell)\ **Post date:** [December 11, 2013, 10:28pm UTC](https://boards.straightdope.com/t/sieve-of-eratosthenes/676097/24 "2013-12-11T22:28:18Z")
> [@DrCube](#): > > A lot of things look simple in hindsight. The genius ideas even more so. Look how long it took to come up with the number zero. Or sliced bread. And that’s kind of the conclusion I came to myself. It’s hard to tell what is “self-evident” when you grow up learning these concepts that you take for granted that may not have been obvious once upon a time. ---
**Author:** ![whc.03grady](https://avatars.discourse-cdn.com/v4/letter/w/a6a055/32.png) [@whc.03grady](https://boards.straightdope.com/u/whc.03grady)\ **Post date:** [December 11, 2013, 10:35pm UTC](https://boards.straightdope.com/t/sieve-of-eratosthenes/676097/25 "2013-12-11T22:35:48Z")
> [@DrCube](#): > > A lot of things look simple in hindsight. The genius ideas even more so. Look how long it took to come up with the number zero. Or sliced bread. True enough, but I think this is different. I learned about primes in 7th grade, maybe 8th, and basically the instant after I heard of the concept, I realized that you could figure out which numbers were prime by seeing if they were evenly divisible by any number smaller than them. That is, by applying the Sieve. I’m not saying I’m extraspecially math smart (obviously–far from it). I’m saying it’s so obvious that that’s how you’d figure out the primes, that it’s weird it has a name. There’s no hindsight here. ---
**Author:** ![whc.03grady](https://avatars.discourse-cdn.com/v4/letter/w/a6a055/32.png) [@whc.03grady](https://boards.straightdope.com/u/whc.03grady)\ **Post date:** [December 11, 2013, 10:38pm UTC](https://boards.straightdope.com/t/sieve-of-eratosthenes/676097/26 "2013-12-11T22:38:13Z")
In fact, I’d go so far as to say that if someone who is given the notion of a prime number for the first time can’t immediately thereafter give you a method for finding them which is equivalent to the Sieve, that they don’t in fact understand the concept of a prime number. ---
**Author:** ![Chronos](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/chronos/32/134_2.png) [@Chronos](https://boards.straightdope.com/u/Chronos)\ **Post date:** [December 11, 2013, 10:42pm UTC](https://boards.straightdope.com/t/sieve-of-eratosthenes/676097/27 "2013-12-11T22:42:18Z")
No, that’s _not_ applying the Sieve. To illustrate, let’s check to see if 5 is prime: Is it divisible by 2? No. Is it divisible by 3? No. Is it divisible by 4? No. OK, it’s not divisible by any of those, so it’s prime. But I did more work than I needed to, there. If I were using the Sieve, instead of just doing the obvious thing, I wouldn’t have had to check 4, because 4 is divisible by 2, and I already checked 2. You don’t have to check _all_ smaller numbers, only the ones that are themselves prime. ---
**Author:** ![whc.03grady](https://avatars.discourse-cdn.com/v4/letter/w/a6a055/32.png) [@whc.03grady](https://boards.straightdope.com/u/whc.03grady)\ **Post date:** [December 11, 2013, 10:47pm UTC](https://boards.straightdope.com/t/sieve-of-eratosthenes/676097/28 "2013-12-11T22:47:58Z")
> [@Chronos](#): > > No, that’s _not_ applying the Sieve. To illustrate, let’s check to see if 5 is prime: > > Is it divisible by 2? No. > Is it divisible by 3? No. > Is it divisible by 4? No. > > OK, it’s not divisible by any of those, so it’s prime. > > But I did more work than I needed to, there. If I were using the Sieve, instead of just doing the obvious thing, I wouldn’t have had to check 4, because 4 is divisible by 2, and I already checked 2. You don’t have to check _all_ smaller numbers, only the ones that are themselves prime. Touche. I oversimplified it above to the point of mangling it. ---
**Author:** ![njtt](https://avatars.discourse-cdn.com/v4/letter/n/ecd19e/32.png) [@njtt](https://boards.straightdope.com/u/njtt)\ **Post date:** [December 11, 2013, 11:41pm UTC](https://boards.straightdope.com/t/sieve-of-eratosthenes/676097/29 "2013-12-11T23:41:20Z")
> [@Kobal2](#): > > I’m sure the sheep herders were thrilled and had a big parade about it, too 🙂 > > But come on, joke aside, read the first line of his Wiki entry, which goes : > and tell me that doesn’t sound like the kind of guy who, should you meet him at a party, is going to bore your ass off then hit you up for money for his next big Project. Or possibly became famous through his MySpace page. > > (BTW, that joke aside bit ? I lied) Eratosthenes was the Librarian of Alexandria, the most powerful academic of his time. _You_ would be trying to hit _him_ up for money for _your_ next project (or, more likely, trying to inveigle your way into a position at the Library). ---
**Author:** ![AaronX](https://avatars.discourse-cdn.com/v4/letter/a/7bcc69/32.png) [@AaronX](https://boards.straightdope.com/u/AaronX)\ **Post date:** [December 11, 2013, 11:41pm UTC](https://boards.straightdope.com/t/sieve-of-eratosthenes/676097/30 "2013-12-11T23:41:45Z")
> [@Chronos](#): > > No, that’s _not_ applying the Sieve. To illustrate, let’s check to see if 5 is prime: > > Is it divisible by 2? No. > Is it divisible by 3? No. > Is it divisible by 4? No. > > OK, it’s not divisible by any of those, so it’s prime. > > But I did more work than I needed to, there. If I were using the Sieve, instead of just doing the obvious thing, I wouldn’t have had to check 4, because 4 is divisible by 2, and I already checked 2. You don’t have to check _all_ smaller numbers, only the ones that are themselves prime. You only need to check up to its square root, don’t you? ---
**Author:** ![Trinopus](https://avatars.discourse-cdn.com/v4/letter/t/2bfe46/32.png) [@Trinopus](https://boards.straightdope.com/u/Trinopus)\ **Post date:** [December 11, 2013, 11:42pm UTC](https://boards.straightdope.com/t/sieve-of-eratosthenes/676097/31 "2013-12-11T23:42:20Z")
> [@whc.03grady](#): > > Okay, all these responses make sense. Maybe I should refine my question. It’s not so much that I’m wondering why it’s named after Eratothenes, but why it’s named at all. It seems like it’s just a restatement of what the definition (or, _a_ definition) of what a prime number _is_: a number not evenly divisible by any smaller positive number except 1. Lots of mathematical techniques don’t have names. How about sorting a group of numbers from lowest to highest? We don’t know who invented it; do I get to claim it as “Trinopus’ Method” now? Leave us not be redickle-dockle! ---
**Author:** ![Hari\_Seldon](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/hari_seldon/32/5173_2.png) [@Hari\_Seldon](https://boards.straightdope.com/u/Hari_Seldon)\ **Post date:** [December 12, 2013, 2:57am UTC](https://boards.straightdope.com/t/sieve-of-eratosthenes/676097/32 "2013-12-12T02:57:43Z")
The sieve is useful if you want a list of all all primes up to, say, 10,000. You write down all the numbers 2 ,…, 10,000, start crossing out all the even ones past 2, all the 3 divisible ones past 3 and so on. After about 40 passes (after you have taken out all multiples of 97), all the remaining numbers will be prime. It also has theoretical uses, leading eventually to one proof of the prime number theorem. ---
**Author:** ![Heracles](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/heracles/32/487_2.png) [@Heracles](https://boards.straightdope.com/u/Heracles)\ **Post date:** [December 12, 2013, 3:00am UTC](https://boards.straightdope.com/t/sieve-of-eratosthenes/676097/33 "2013-12-12T03:00:27Z")
I learned about prime numbers probably around age 10. Yes, you can figure out if each number is divisible by two using the Filter of Grady ™. Yes, you can try to divide by 3, by 5, by 7, etc. and see if there’s a remainder. Yes, you can stop searching when you get to the square root. No, we won’t discuss numbers above 500, so it shouldn’t be too hard. No, we won’t try to make a list of primes, we’d have to decompose every one like that, it would take months. I learned about the Sieve around age 18. I found it quite ingenious, and different from the methods I just described above. ---
**Author:** ![Chronos](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/chronos/32/134_2.png) [@Chronos](https://boards.straightdope.com/u/Chronos)\ **Post date:** [December 12, 2013, 3:12am UTC](https://boards.straightdope.com/t/sieve-of-eratosthenes/676097/34 "2013-12-12T03:12:09Z")
> [@](#): > > Quoth **Trinopus** : > > Lots of mathematical techniques don’t have names. How about sorting a group of numbers from lowest to highest? We don’t know who invented it; do I get to claim it as “Trinopus’ Method” now? What technique are you referring to for that? There are a lot of techniques for [sorting a list of numbers](http://en.wikipedia.org/wiki/Sorting_algorithm), the most obvious ones are all rather poor, and for most of the methods that are actually decent, we do know who invented them. ---
**Author:** ![Trinopus](https://avatars.discourse-cdn.com/v4/letter/t/2bfe46/32.png) [@Trinopus](https://boards.straightdope.com/u/Trinopus)\ **Post date:** [December 12, 2013, 3:14am UTC](https://boards.straightdope.com/t/sieve-of-eratosthenes/676097/35 "2013-12-12T03:14:42Z")
I’m rather fond of “bogosort.” You take the list, randomize it, and then check to see if it is sorted. If it isn’t, you repeat. The process exits when the list is sorted. (This works on the principle that it takes much less time to determine if a list is sorted than it takes to sort the list. Much less time if bogosort is your sorting algorithm.) For something more efficient, do you know “spaghetti sort?” ---
**Author:** ![Thudlow\_Boink](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/thudlow_boink/32/320_2.png) [@Thudlow\_Boink](https://boards.straightdope.com/u/Thudlow_Boink)\ **Post date:** [December 12, 2013, 3:21am UTC](https://boards.straightdope.com/t/sieve-of-eratosthenes/676097/36 "2013-12-12T03:21:58Z")
> [@Hari\_Seldon](#): > > It also has theoretical uses, leading eventually to one proof of the prime number theorem. I don’t remember hearing about this before. I’m intrigued, but also intimidated: this can’t be simple or obvious, given the enormous historical gap between the Sieve of Eratosthenes and the proof of the Prime Number Theorem. ---
**Author:** ![KarlGauss](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/karlgauss/32/3713_2.png) [@KarlGauss](https://boards.straightdope.com/u/KarlGauss)\ **Post date:** [December 12, 2013, 3:28am UTC](https://boards.straightdope.com/t/sieve-of-eratosthenes/676097/37 "2013-12-12T03:28:31Z")
Phew . . . it took me a while, but, I think I figured it out. 54,898,390,234,005,943,587,727,239,987,774,321,490,934,981 = 149 \* 5,057,851,586,423 \* 253,029,274,165,763 \* 287,896,569,700,381 You may wanna double check my math. ---
**Author:** ![pulykamell](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/pulykamell/32/3166_2.png) [@pulykamell](https://boards.straightdope.com/u/pulykamell)\ **Post date:** [December 12, 2013, 3:45am UTC](https://boards.straightdope.com/t/sieve-of-eratosthenes/676097/38 "2013-12-12T03:45:54Z")
> [@KarlGauss](#): > > Phew . . . it took me a while, but, I think I figured it out. > > 54,898,390,234,005,943,587,727,239,987,774,321,490,934,981 = 149 \* 5,057,851,586,423 \* 253,029,274,165,763 \* 287,896,569,700,381 > > You may wanna double check my math. 🙂 I’m not going to check, but I think that’s what Wolfram Alpha told me as well. ---
**Author:** ![KarlGauss](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/karlgauss/32/3713_2.png) [@KarlGauss](https://boards.straightdope.com/u/KarlGauss)\ **Post date:** [December 12, 2013, 3:51am UTC](https://boards.straightdope.com/t/sieve-of-eratosthenes/676097/39 "2013-12-12T03:51:05Z")
I forgot about Wolfram so used [this](http://www.numberempire.com/numberfactorizer.php). ---
**Author:** ![Indistinguishable](https://avatars.discourse-cdn.com/v4/letter/i/90ced4/32.png) [@Indistinguishable](https://boards.straightdope.com/u/Indistinguishable)\ **Post date:** [December 12, 2013, 4:44am UTC](https://boards.straightdope.com/t/sieve-of-eratosthenes/676097/40 "2013-12-12T04:44:02Z")
A number of people are missing a significant point about the Sieve of Eratosthenes which makes it more sophisticated than simply applying the grade-school definition of “prime”: as **Chronos** noted, the Sieve of Eratosthenes works not by testing a number for _any_ smaller factors, but rather, by only testing it for smaller _prime_ factors. Obvious? Hey, everything’s obvious after you get familiar with it. But that efficiency gain is nothing to sneer at. [Previous page](https://boards.straightdope.com/t/sieve-of-eratosthenes/676097.md?page=1) [Next page](https://boards.straightdope.com/t/sieve-of-eratosthenes/676097.md?page=3)