Ponderous primality testing [closed]

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 ≈ 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.

Scoring

This is a , 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.

closed as too broad by trichoplax, Conor O'Brien, El'endia Starman, Alex A.Apr 7 '16 at 17:54

Please edit the question to limit it to a specific problem with enough detail to identify an adequate answer. Avoid asking multiple distinct questions at once. See the How to Ask page for help clarifying this question. If this question can be reworded to fit the rules in the help center, please edit the question.

• How does one determine idleness or useless code? – Addison Crump Apr 7 '16 at 16:46
• This could be a decent challenge, but it feels just a little bit too close to code-trolling. – DJMcMayhem Apr 7 '16 at 16:55
• While this challenge doesn't bear the tag, it is arguably an underhanded contest, which are off-topic per community consensus. – Dennis Apr 7 '16 at 16:56
• You scrubbed the word underhanded from the specification, but the intentions remain. If the reason for the code's slowness has to be obfuscated, the contest is underhanded. – Dennis Apr 7 '16 at 17:23
• @Dennis: (1) This was never intended as an underhanded challenge. (2) The code is not supposed to be obfuscated in any way -- I don't intend (and haven't intended) to vote for obfuscated code. (3) The only place I ever mentioned any of this was in the recommendations to voters -- they are entirely optional. The purpose of that bullet point was to encourage creativity, not to troll. (If I wanted to be underhanded I would ask for code which ran quickly for most inputs and slowly for a tiny fraction -- clearly code which runs at glacial speed would be discovered immediately on execution.) – Charles Apr 7 '16 at 18:19

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