Prime Number Library for OCaml

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.

One thought on “Prime Number Library for OCaml

Leave a Comment