A couple of weeks ago, I cleaned up my prime number library for OCaml. This library has a number of primality-testing methods in it, but my favorite is the Miller-Rabin primality test. It’s fast and rather accurate.

If you’d like to take a look at the library, please check out the camlprime GitHub page. The library is pretty easy to use. If you download and compile the library, you’ll end up with a toplevel that you can play with.

The test.ml file has some examples of how to use the primality tests. However, my favorite thing about this library is that it includes a lazy list implementation of prime numbers. The following example shows how to set up a lazy list of prime numbers proved using the MR algorithm in the toplevel.

# open Num ;;
# let prime_list = Prime.make (Prime.miller_rabin 500) (num_of_int 500) ;;
val prime_list : Num.num LazyList.t = LazyList.Node (Int 503, <lazy>)
# Prime.nth prime_list 500 ;;
- : Num.num = Int 4363

The library is pretty fast, even for really large numbers. I’ve tested it on 300-digit prime numbers, and I’m sure it will scale to sizes much larger than that.

Any thoughts or improvements? Let me know in the comments.