Ponderous primality testing [closed]

Question

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:

Nathan's algorithm

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 ≈ 10⁴ divisions to test 10007, the smallest 5-digit prime. By contrast, Nathan's algorithm takes more than 10³⁷⁰ divisions, making it 10³⁶⁶ 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.

Scoring

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.

Answer 1

Python 2, Really slow

import time

def isPrime(n):
    if type(n) is not int: return False
    if n < 2: return False
    if n == 2: return True
    has_composite_factor = False
    for i in range(2, n):
        i_is_prime = isPrime(i)
        if n % i == 0:
            if not has_composite_factor and i_is_prime:
                has_composite_factor  = True
    return not has_composite_factor 

def time_it(n):
    start = time.clock()
    prime = isPrime(n)
    end = time.clock()
    
    return end - start

for i in range(20, 30):
    print "{}: {}".format(i, time_it(i))

If a number is prime, it stands to reason that all of it's factors must also be prime. If we can find a single composite factor, then this number cleary isn't prime. We must also check to see if the number is valid, which is why we check type(n) and n < 2.

This runs decently fast on n < 20 but takes several seconds once you hit 25. Here is how long it takes to calculate 20-30:

20: 0.141494
21: 0.282143
22: 0.565975
23: 1.132836
24: 2.266971
25: 4.525667
26: 9.050018
27: 18.110675
28: 36.372516
29: 72.920298