99 Clojure Problems – 31: Determine Whether a Given Integer Number Is Prime

Example

(deftest p31-test-primes
  (is (not (prime? 4)))
  (is (prime? 7)))

Solution

My first solution is based on the straight forward approach of testing for divisibility by all integers starting with 2 until sqrt(n). If a number is prime it will be only divisible by itself (and 1).

My second solution is a translation of a primality test based on Fermat's Little Theorem as outlined in SICP 1.2.6. It says that a number n is certainly not prime if raised to a random positive integer a less than n and divided by n is not equal to a.

This second approach is faster for large numbers but it is a probabilistic algorithm. This means in our case if the remainder of a^n divided by n is a, the number n is only probably a prime. While the probability gets higher every time we successfully run the test with another number, there is no "guarantee".

In addition the Fermat test can be fooled by a couple of extremely rare numbers (called Carmichael numbers). Read the relevant chapter in SICP for more on this topic.

Read more about this series.