I'm looking for an algorithm or three to use in testing for prime numbers. I'm most concerned about those representable as ints or longs (that is, less than 2^63). In that range, what tests are efficient? At the moment, I'm using a combination of: * The naive division algorithm with a precomputed list of primes (the empyrically-derived cutoff is 5,500,000, checking primes up to 2341). * Strong n-probable prime tests, plus bounds due to Jaeschke that turn this into a determanistic test. (2- and 3- SPrPs below 1,373,653 are prime; 2-, 3-, and 5- SPrPs below 25,326,001 are prime; 2-, 3-, 5- and 7- SPrPs below 118,670,087,467 are either 3,215,031,751 or prime; etc.) The problem is that I don't know how to extend the latter test beyond 341,550,071,728,321 (testing all the primes up to 17), and I don't know if there's a faster method at some cutoff. Any help here? Edit: Bleichenbacher has numbers that extend this test to 10^16, but I'd still like to go higher. Any thoughts?