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

Obligatory

[zedmelon]

This article will be a prime target for bad jokes.

Re:Obligatory

[Anonymous Coward]

We must not be divided on this issue.

Re:Where is it?

[canwaf]

Sorry, 404 isn't a prime number. Try again.

Re:This begs the question:

[Anonymous Coward]

Why waste disk space with primes instead of just recalculating them?

Re:the factor command in Unix/Linux

[0racle]

You don't really have friends do you.

Not as much fun as

[Snoe]

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.

How to prove that all odd numbers are prime

[dargaud]

"It was mentioned on CNN that the new prime number discovered recently is four times bigger than the previous record." --John Blasik

"You know what seems odd to me? Numbers that aren't divisible by two." --Michael Wolf.

"I don't get even, I get odder."

How to prove that all odd numbers are prime? Well, this problem has different solutions whether you are a:

• Mathematician: 1 is prime, 3 is prime, 5 is prime, 7 is prime, and by induction we have that all the odd integers are prime.
• Physicist: 1 is prime, 3 is prime, 5 is prime, 7 is prime, 9 is an experimental error...
• Engineer: 1 is prime, 3 is prime, 5 is prime, 7 is prime, 9 is prime...
• Chemist: 1 prime, 3 prime, 5 prime... hey, let's publish!
• Modern physicist using renormalization: 1 is prime, 3 is prime, 5 is prime, 7 is prime, 9 is ... 9/3 is prime, 11 is prime, 13 is prime, 15 is ... 15/3 is prime, 17 is prime, 19 is prime, 21 is ... 21/3 is prime...
• Quantum Physicist: All numbers are equally prime and non-prime until observed.
• Professor: 1 is prime, 3 is prime, 5 is prime, 7 is prime, and the rest are left as an exercise for the student.
• Confused Undergraduate: Let p be any prime number larger than 2. Then p is not divisible by 2, so p is odd. QED
• Measure nontheorist: There are exactly as many odd numbers as primes (Euclid, Cantor), and exactly one even prime (namely 2), so there must be exactly one odd nonprime (namely 1).
• Cosmologist: 1 is prime, yes it is true....
• Computer Scientist: 1 is prime, 10 is prime, 11 is prime, 101 is prime...
• Programmer: 1 is prime, 3 is prime, 5 is prime, 7 is prime, 9 will be fixed in the next release, ...
• C programmer: 01 is prime, 03 is prime, 05 is prime, 07 is prime, 09 is really 011 which everyone knows is prime, ...
• BASIC programmer: What's a prime?
• COBOL programmer: What's an odd number?
• Windows programmer: 1 is prime. Wait...
• Mac programmer: Now why would anyone want to know about that? That's not user friendly. You don't worry about it, we'll take care of it for you.
• Bill Gates: 1. No one will ever need any more than 1.
• ZX-81 Computer Programmer: 1 is prime, 3 is prime, Out of Memory.
• Pentium owner: 1 is prime, 3 is prime, 5 is prime, 7 is prime, 8.9999978 is prime...
• GNU programmer: % prime
  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''
• Unix programmer: 1 is prime, 3 is prime, 5 is prime, 7 is prime, ...
  Segmentation fault, Core dumped.
• Computer programmer: 1 is prime, 3 is prime, 5 is prime

Re:This begs the question:

[StyroCupMan]

If each number only has a 0.000703 chance of being prime, we can simplify this whole calculation with this function (pseudo-coded):

boolean isPrime(int Number) {
return false;
}

That function is 92.97% accurate. That's an A-. Good enough for me. :)