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?

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.