Quote:
Originally Posted by Zach010
An algorithm that works 100.0% of the time and is fast?

Yes. For example, the next prime after the Mersenne prime tested above is 2^61 + 15. PARI/GP proves its primality in 500 nanoseconds.
Moving to somewhat larger numbers, PARI/GP takes 150 ms to prove that 10^100 + 267 is prime. How long do you project that would take your program, assuming you networked all the computers in the world for the task?