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.
Yes, thank you, that is what I meant. “Looking” as in “checking”, which, I guess, constitutes applying an algorithm.
Exactly.
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.
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.
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.
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.
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).
You only need to check up to its square root, don’t you?
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!
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.
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.
What technique are you referring to for that? There are a lot of techniques for sorting a list of numbers, the most obvious ones are all rather poor, and for most of the methods that are actually decent, we do know who invented them.
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?”
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.
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.
I forgot about Wolfram so used this.
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.