One of my favorite algorithms was posted on Stack Overflow as an answer to What is the fastest way to generate prime number recursively?. In pseudocode:
bool isPrime(int n): if (n < 2) return false for p in 2..n-1: if (isPrime(p) && n%p == 0) return false return true
This program is lovely because it doesn't have any wasted steps (in the author's words, "it's quite efficient because it only needs to test the prime factors") but still manages to take far longer than any reasonable algorithm. For example, compare the naive algorithm:
Unoptimized trial division
bool isPrime(int n): if (n < 2) return false for p in 2..n-1: if (n%p == 0) return false return true
This requires 10005 ≈ 104 divisions to test 10007, the smallest 5-digit prime. By contrast, Nathan's algorithm takes more than 10370 divisions, making it 10366 times slower. If every electron was a 1-googol GHz computer, and this program had been running across all electrons in the universe since the Big Bang, it wouldn't even be close to 1% done.
The task is to write a program, in the language of your choice to test if a given number is prime as slowly as possible. The programs may not simply waste time by idling or executing unused loops; it should be clever in its sloth.
This is a popularity-contest, so the (valid) answer with the most votes wins. Golfing is neither required nor recommended. Suggested criteria for voting:
- Creativity: How does the program manage to do so much work?
- Originality: Does the program use a novel approach?
- Reasonableness: Does the code look reasonable at a glance? It's best if there are not sections which could obviously be excised to speed it up.
- Simplicity: A single, well-executed idea is better than a combination of unrelated ideas (though cleverly combining approaches is encouraged).
I consider Nathan's program to embody all four principles. As such, if the original author posts the original program here I will upvote it.