Mod 6 Primality Test
Observe that all primes greater than 3 are of the form , where k is any integer greater than 0.
This is because all integers can be expressed as where . Note that 2 divides 6k and 6k + 2 and 6k + 4, 3 divides 6k + 3. So, a more efficient method is to test whether n is divisible by 2 or 3, then to check through all numbers of the form . This is 3 times faster than testing all numbers up to
Fermat Test
Use Fermat’s Little Theorem, a Probability algorithm.