Where "fast" is defined as "involves disk reads" and "prime numbers" should have the qualifier "under 200." The algorithm is brute force testing of all values up to sqrt(n), which is worse than the one the ancient Greeks used.
Behold, MR.Prime!<p><a href="https://github.com/rkneufeld/mr_prime" rel="nofollow">https://github.com/rkneufeld/mr_prime</a><p>It's a little ruby Miller-Rabin primality tester I wrote with my friend in Crypto class that can handle ~500 digit primes in less than a few seconds. I think my friend also wrote a C extension for it - super fast.<p>Edit: spelling.