Fun with Prime Numbers

Steve Litt writes "Fun With Prime Numbers contains a series of prime number finding algorithms starting with the most brute force imaginable, and working up to a paged algorithm capable of finding the first 1,716,050,469 primes in an hour and a half on a commodity machine. There are faster algorithms on the net, but these algorithms are within the reach of mere mortals and are fully explained."

Comments

This begs the question:

[Anonymous Coward]

Why not just save primes on a disk instead of recalculating them all the time?

Re:This begs the question:

[psetzer]

Actually, in the final implementation, I thought that he does that. It creates a few thousand files, each one containing n primes, and then it goes through each previous file up to the square root of the largest number in the current file, and then it quits and goes to the next file. If you want to duplicate this guy's efforts, I think that the biggest help for this would be a REALLY fast HD array and lots of RAM.

What is special about prime numbers?

[Dancin_Santa]

I understand that number sequences like Fibonacci manifest themselves in Nature and others like pi provide a fairly decent random number generation method. However, aside from the interesting property that they can't be divided by anything other than themselves and 1, I do not 'get' what is interesting or useful about prime numbers.

But then again, I haven't studied mathematics to any great extent beyond the multi-var calc and linear algebra back in high school. That was such a long time ago. Any math Geniuses out there want to clue is in on why primes are interesting?

That's nice, but...

[gibs]

Can someone tell me again what the point of this is?

Re:Complaint about article

[shamilton]

The article feels like it was written for the sole purpose of showing off the author's knowledge. Perhaps I'm just hyper-sensitive to that...

Improvement

[acidblood]

Blockquoth the FA's author, regarding how to store a list of primes:

Keeping it in an array is simplest, but one must declare the array before finding primes. How big do you declare it.

Have a look here for a pretty tight upper bound on the number of primes up to a given number. Using an array, instead of a linked list, would probably lead to a small speed improvement on his code.

He could also use an std::vector from C++. As far as I can tell it's pretty easy to resize.

also doesn't make sense

[Trepidity]

Shouldn't any decent optimizing compiler (gcc?) inline those commonly-called functions anyway?

That's their usefulness

[Anonymous Coward]

But where is their beauty? Like was mentioned before, fibonacci shows up all over the place, pi is at the core of almost everything, and you can't take a look at anything without visualizing the Golden Mean.

The use of prime numbers in encryption is fine and dandy, but no more complex than using something simple like Blowfish which is essentially a one-time pad. A thing's application does not establish its beauty.

There was a post above that pointed to a pictograph of primes plotted in a spiral manner in which diagonal streaks were visible, but that seems a wee bit contrived. Primes seem to be an interesting property of numbers, but they do not seem to have a natural "manifestation" which would grant them beauty.

Re:Give it up; this battle is a lost cause.

[BJH]

If the primary existence of the Earth was as a collective consensus among humans, yes.

You're comparing apples and oranges here. Language does not exist as an objective reality; it relies entirely upon the internal representation of that language shared between its speakers. If in the future nobody understood that language, it would no longer "exist" in any meaningful sense, whereas the Earth exists independently of the internal reality any human (or other being) holds to be true.

In other words, the only way a language can be said to exist is as a "mainstream belief" of its speakers. So, you lose.