Slashdot Mirror
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."
This article will be a prime target for bad jokes.
Mom says my
Sorry, 404 isn't a prime number. Try again.
Why waste disk space with primes instead of just recalculating them?
Find out more on the Nth Prime Page.
From the article:
... * 65537 + 2 = 2 * (3 * ... * 65537 + 1) ... * 65537 + 3 = 3 * (2* 4 * ... * 65537 + 1)
...
... * 65536 * 65537 + 65537 = 65537(65536!+1)
..., 65537! + 65537 are all nonprime (the first is divisible by 2, the second by 3, the thrid by 4 etc). Since we also know that there are infinitely many primes, there must be a prime greater than 65537! + 65537. The biggest prime less than 65537! + 2 and the least prime bigger than 65537! + 65537 are consecutive primes which are at least 65536 apart.
..., 6! + 5} ={722, 723, 724, 725, 726} are all nonprime, but also 24, 25, 26, 27, 28 are 5 consecutive nonprime numbers.
who can be sure that there aren't two consecutive primes somewhere that are more than 65536 apart
Let's recall elementary number theory:
65537! + 2 = 2 * 3 *
65537! + 3 = 2 * 3 *
65537! + 65537 = 2* 3 *
So the 65536 consecutive numbers 65537! +2 ,
Of course, 65537! is a massive number, which is unlikely to crop up in these calculations. There may be other sufficiently large gaps between primes among smaller numbers.
Consider, for instance, the method above applied with 5 in the place of 65536. We see that {6! +2,
For where we can expect large 'prime-free' gaps, I'll defer to any number theorist.
You don't really have friends do you.
"I use a Mac because I'm just better than you are."
Yeah, but that's an example of them being useful. It doesn't really make them esthetically "interesting".
In that case I refer you to the fundamental theorum of arithmetic, which I think is pretty interesting.
Vino, gyno, and techno -Bruce Sterling
I do not 'get' what is interesting or useful about prime numbers.
...)= ((1-2^(-2))*(1-3^(-2))*(1-5^(-2))...)
There is therefore a connection between pi and the distribution of the primes. Math is crazy stuff.
Prime numbers are useful in encyption, but those are very large primes that are difficult to factor. To a mathematician, prime numbers are fascinating. The distribution of primes, which is specifially random but generally predictable (check out the MathWorld article for more details) is of particular interest.
For example, the Riemann Zeta Function of n, which is the infinite sum of all terms k^(-n)[k varies from one to infinity], is expressable as the infinite product (1-p1^(-n))*(1-p2^(-n))*(1-p3^(-n))... [where pn is the nth prime number]. This is a mind-boggling connection. For example Zeta(2)= (pi^2)/6 = (1 + 1/2 + 1/4 +1/8
The Prime Number Shitting Bear. Watching a console window spit out prime numbers might do it for the geeks, but everyone can loves the prime number shitting bear.
...and I'm going to list a few improvements here that I think the author missed.
In one of the early programs, the author had the idea of skipping all even numbers, which are of course divisible by 2. In the next program he found out how he could skip numbers divisible by 3. One can make a systematic method out of that -- in the literature it's known as adding a wheel to the sieve of Erathostenes. Thing is, he implemented the sieve of Erathostenes foregoing this improvement he had implemented earlier. This leads to a big improvement: when using a wheel with the first four primes 2,3,5,7, there are only 48 residue classes out of 210 = 2*3*5*7 possible that are not divisible by any of these four primes. In practice this means that, for each 210 numbers you'd consider, the sieve would only need be applied in 48 of them. That's a gain of 4.375. One can make a gain of nearly 5 using a wheel of the first five primes, but it begins to get complicated.
Another improvement would be to make the program cache-friendly. He sort of did this, down one level of the memory hierarchy, by paging the data to disk -- now he only needed to realize that, just as memory is much faster than disk, cache memory is faster than main memory. I've developed a sieve employing this optimization and it pays off indeed. This is considered a basic technique in the realm of high-performance computing. (The NFSNET, see my sig, uses a sieve including this and other optimizations, for instance).
I might get flamed for this, but he should consider assembly programming. There aren't many applications where assembly will pay off so handsomely as this one, and the `core' of the sieve is very small, so only a few lines of assembly are needed. Vector integer instructions, such as MMX and the integer instructions of SSE2, can be employed to very good advantage here. My sieve program also included this, and it gives a real nice boost -- and only about 25 lines of assembly were used, the rest was C.
Lastly there's the issue of representing the output. He stored the primes on disk by writing their values. A little compression can be realized in this representation: for instance he's printing out the primes in decimal, while hexadecimal would be more space-efficient. And instead of printing out the ASCII characters from 0 to 9, A to F, he could use a binary representation and read them through an hex dump -- that saves half the space, as a byte is used to store two hexadecimal digits instead of one.
A perfectly good representation that could save a lot of space (8 times, to be precise) would be a bitmap, which he used on some of his programs. That's where you represent primality or lack of it by setting and clearing bits of an integer. It's pretty easy to determine a prime from a bitmap value, so this representation is just as good as the previous one. One could also use the wheel idea I explained before to save even more space: a concrete example would be that for each block of 210 numbers, one needs only bitmaps for 48 of them, as the rest are divisible by the first four primes. In this example a savings of 4.375 would be realized. Of course, all these ideas would require special readers programs, instead of just opening up the files in a text editor -- a small price to pay for such a large space savings.
But in case only sequential reading of the primes is desired, there is an even more efficient representation: just write out the prime gaps, i.e. the difference between consecutive primes. One bit can be saved by realizing that, other than 3 - 2, all prime gaps are even, so one can just store the prime gap divided by two. One could really nitpick and point out that 0 is an impossible prime gap, so one could subtract two from all gaps, but this gain is too small to be worth the hassle. According to Thomas Nicely (incidentally the guy who discovered the bug on the Pentium FPU during his studies on computational number theory), one could store the prime gaps of all
Join the NFSNET. Our prime goal is making little numbers out of big ones. http://www.nfsnet.org/
How to prove that all odd numbers are prime? Well, this problem has different solutions whether you are a:
usage: prime [-nV] [--quiet] [--silent] [--version] [-e script] --catenate --concatenate | c --create | d --diff --compare | r --append | t --list | u --update | x -extract --get [ --atime-preserve ] [ -b, --block-size N ] [ -B, --read-full-blocks ] [ -C, --directory DIR ] [--checkpoint ] [ -f, --file [HOSTNAME:]F ] [ --force-local ] [ -F, --info-script F --new-volume-script F ] [-G, --incremental ] [ -g, --listed-incremental F ] [ -h, --dereference ] [ -i, --ignore-zeros ] [ --ignore-failed-read ] [ -k, --keep-old-files ] [ -K, --starting-file F ] [ -l, --one-file-system ] [ -L, --tape-length N ] [ -m, --modification-time ] [ -M, --multi-volume ] [ -N, --after-date DATE, --newer DATE ] [ -o, --old-archive, --portability ] [ -O, --to-stdout ] [ -p, --same-permissions, --preserve-permissions ] [ -P, --absolute-paths ] [ --preserve ] [ -R, --record-number ] [ [-f script-file] [--expression=script] [--file=script-file] [file...]
prime: you must specify exactly one of the r, c, t, x, or d options
For more information, type "prime --help''
Segmentation fault, Core dumped.
Non-Linux Penguins ?
That function is 92.97% accurate. That's an A-. Good enough for me.
If I may say so, life is a game, and there's so much to do and so few turns.
-Reiner Knizia