Sieve of Eratosthenes

[kferr]

@Trinopus

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?”

During my first two years of University we did our programming on punch cards. dropping your card deck often necessitated a “floor sort”.

[Buck_Godot]

@pulykamell

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.

I agree, way back in 1988 in my high school pascal programming class, we had the project to find all primes less than 1000, and an informal contest to have the shortest run time. The obvious algorithm would be test each number consecutively for divisibility of all previously identified primes. This was blown out of the water by the sieve which didn’t have to divide and check for a remainder.

[Skald_the_Rhymer]

@whc.03grady

What’s so special about the Sieve of Eratothenes that it even gets a name? I can’t imagine that the first time someone has the concept of a prime number explained to them, that this sorting method isn’t basically the next thing that pops into their head. It seems so obvious; how could Eratosthenes’ve been the first guy to come up with it?

(On a side note, I propose a “Filter of Grady” as a way of figuring out which numbers are even: If they end in 0, 2, 4, 6, or 8, they’re even. There, I did it.)

Lots of things seem obvious once someone else figures it out.

[Andy_L]

@Skald_the_Rhymer

Lots of things seem obvious once someone else figures it out.

Speaking of reinvented the wheel, remember “Tai’s Method” Is this a serious academic paper? - Miscellaneous and Personal Stuff I Must Share - Straight Dope Message Board

[dtilque]

@Buck_Godot

I agree, way back in 1988 in my high school pascal programming class, we had the project to find all primes less than 1000, and an informal contest to have the shortest run time. The obvious algorithm would be test each number consecutively for divisibility of all previously identified primes. This was blown out of the water by the sieve which didn’t have to divide and check for a remainder.

This is even more significant for human processing than for computer, especially at the time the Sieve was discovered.

Most people think of division as one of the simple mathematical functions. OK, it’s not as simple as addition, but they teach it to fourth graders, so it can’t be that hard. But we wouldn’t be teaching them that if it weren’t for the Arabic numbers. Before they came along, division of more than 1 or 2 digit numbers[sup]1[/sup] was difficult. So difficult that it was considered advanced mathematics.

So the Sieve was a way to find prime numbers without division. In fact without doing anything more complicated than counting. This would have been an incredible advance and one that was likely only obvious in hindsight. I think it deserves the name of its discoverer.
[sup]1[/sup] I assume they memorized the multiplication tables up to at least 100, just as we do today. If they didn’t then division of 1 and 2 digit numbers would have been difficult as well.

[Lemur866]

I think dtilque has figured it out. We think division is easy. It is, kinda, using Arabic numbering. But using older numbering systems division is very difficult, and so is multiplication. So finding out whether a large arbitrary number is divisible by another arbitrary large number wasn’t as computationally easy as we think back in Greek and Roman and Babylonian days.

[TimeWinder]

@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.

Yeah, you’re right. I can tell by just looking I find it a little amusing, though, that the factors other than 149 are all so large – just a coincidence, since as I’m sure you guessed, I just typed numbers at random.

[leahcim]

@TimeWinder

I find it a little amusing, though, that the factors other than 149 are all so large – just a coincidence, since as I’m sure you guessed, I just typed numbers at random.

Not entirely a coincidence. I recall that the average number of prime factors of a number grows very slowly in the size of the number (logarithmically or maybe log-integrally), so numbers with a few, mostly large factors are the norm, and numbers like 2^50*3^75 are rare.

ETA: This is what I might have been remembering: Hardy–Ramanujan theorem - Wikipedia

[Enola_Straight]

Except for 2 and 3, all primes are some multiple of 6, plus or minus 1.
http://french.chass.utoronto.ca/as-sa/ASSA-14/modulus6-spiral90.jpg

SO…

Remove elements divisible by 2 and 3,
whats left, remove elements divisible by 5 and 7, 11 and 13, 17 and 19, etc.

Thus, we have the Colander of Enola.

[ultrafilter]

@Indistinguishable

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.

Yes. Everyone who didn’t read this post needs to do so.

@whc.03grady

(On a side note, I propose a “Filter of Grady” as a way of figuring out which numbers are even: If they end in 0, 2, 4, 6, or 8, they’re even. There, I did it.)

How’s that work in base 7?

[Itself]

The point of the Sieve is that if you want to check whether a positive number n is prime, you don’t have to test whether it’s divisible by all m < n; you just have to check whether it’s divisible by all prime m < n. If you go through the integers crossing off obviously composite numbers as you go, you save a bit of work. Is it profound,or even anything more than a simple and obvious trick? Of course not, but no one’s claiming it is.

[njtt]

The most profound discoveries are often the ones that seem most obvious in retrospect.

[Thudlow_Boink]

@Itself

The point of the Sieve is that if you want to check whether a positive number n is prime, you don’t have to test whether it’s divisible by all m < n; you just have to check whether it’s divisible by all prime m < n.

Yes, but in reverse: you don’t start with each number and check whether it’s divisible by various primes; you start with each prime and eliminate each number that’s divisible by that prime—which is easier, especially if you don’t have modern notation for writing numbers and doing division, because it can be done simply by counting (as several of us have already pointed out).