primes.mli indicates the implementation is 1000 (!) iterations of Miller-Rabin.

README.md indicates the test is AKS.

primes.ml seems to implement an exponential time binomial test, which is a very inefficient way to implement naive trial division. Perhaps this idea came from the numberphile video, which incorrectly describes this opening lemma as AKS (it is not), or from the Rosettacode page which is incorrectly named.

This repo is mentioned as the upstream for the opam package called primes. However, for some reason I failed to see, the package available on opam (OCaml 4.06.1) is not at all in sync with this repo.

me@home:~$ opam update
me@home:~$ opam show primes
             package: primes
             version: 1.3.5
          repository: default
        upstream-url: https://github.com/KitFreddura/OCaml-Primes/archive/1.3.5.tar.gz
       upstream-kind: http
   upstream-checksum: 583f2e27c00a06465719ae84aa4f79f2
            homepage: https://github.com/KitFreddura/OCaml-Primes
         bug-reports: https://github.com/KitFreddura/OCaml-Primes/issues/new
            dev-repo: https://github.com/KitFreddura/OCaml-Primes.git
              author: Kit Freddura <[email protected]>
             license: MIT License
             depends: ocamlfind & zarith & gen
   installed-version: 
  available-versions: 1.3.3, 1.3.5
         description: A small library for dealing with primes.

Primes is a library for finding and testing prime numbers in OCaml, see the .mli file for interface details. Please check out the git for issues, concerns, suggestions or if you wish to contribute!
me@home:~$ opam install primes

So I got version 1.3.5, although the latest version is 1.3.3 according to the opam file in this repo. The interface I got through opam is missing important bits:

utop # #show Primes ;;
module Primes :
  sig
    val big_primes : int -> Z.t list
    val primes : int -> int list
    val is_prime : int -> bool
    val prime_factors : int -> int list
  end

Functions big_is_prime and miller_rabin_test are missing (the first one is missing from the .mli file even in this repo).

Even worse, function is_prime is seriously flawed (but seemingly not because of a dummy implementation, because returning true still takes quite a long time):

utop # for n = 1 to 4_000 do assert (Primes.is_prime n) done ;;
- : unit = ()

So what’s going on?

'is_prime' seems working only for 2-3-5-7-11-13-17 and 19
(23 -> false - therefore 'prime-factors 23' gives the wrong list [] ). Interesting !

Note 1 : please don't use Core for the only '~f:' syntax. This is crazy :)
You can have the same result with the (one and only) OCaml Standard Library by writing
'ListLabels.filter ...' or 'ListLabels.map ...'.
(Suppress Core but add 'Gen' as dependency in your README.md file)

Note 2 : your source code is ugly: lot of useless whitespaces and a bad
indentation. (I suggest 'opam install ocp-indent'. ocp-indent can be integrated in your editor
or can be used as a separate program)

needs one. badly. @KitFreddura - I'm indifferent. Can we settle on one for this project so tests can be written for the critical functions?

Might be worth functorizing over the numerical type so you can generate different versions of the top level api. (The inner api can be a specific numerical type though if it makes sense, probably zarith as sometimes the calculations exceed int space even if the answer does not).

Problem

using dune to compile my module using primes:

gcc: error: /home/opam/.opam/5.0/lib/primes/primes.a: No such file or directory

Research

$ ls -al /home/opam/.opam/5.0/lib/primes/
total 536
drwxr-xr-x 2 opam opam   4096 Sep  5 18:27 .
drwxr-xr-x 1 opam opam   4096 Sep  5 18:33 ..
-rw-r--r-- 1 opam opam    159 Jul 26  2016 META
-rw-r--r-- 1 opam opam 484074 Sep  5 18:25 primes.cma
-rw-r--r-- 1 opam opam    849 Sep  5 18:24 primes.cmi
-rw-r--r-- 1 opam opam   2643 Sep  5 18:25 primes.cmo
-rw-r--r-- 1 opam opam   5217 Sep  5 18:24 primes.cmti
-rw-r--r-- 1 opam opam   1012 Sep  5 18:25 primes.cmx
-rw-r--r-- 1 opam opam    585 Sep  5 18:25 primes.cmxa
-rw-r--r-- 1 opam opam    782 Jul 26  2016 primes.mli
-rw-r--r-- 1 opam opam  13872 Sep  5 18:25 primes.o

I imagine that we want to make signatures for various common number theoretic functions or tests, if only to make the api manageable as different implementations arise. Maybe something like this for prime testing?

(* Number.ml- we may be able to find this interface in Base or Containers *)
module type S =
sig
type t
val add : t -> t -> t
(* ... etc. *)
end

(* Optional_args.ml  *)
module type S =
sig
  type t           (** type of default argument. *)
  val default : t   (** A default value used when not specified.*)
end

(* Primes.ml *)
module type S = 
sig
  module Number : Number.S
  module Optional_args : Optional_args.S
  val is_prime : ?Optional_args.t -> Number.t -> bool
end

(* Random brute force example *)
module Iter_args = struct type t = {max_iters:int} let default = {max_iters=1000} end 

module Brute_force : Primes.S with 
  module Number = Z and 
  module Optional_args = Iter_args = 
struct
    module Number = Z
    module Optional_args = Iter_args
    open Optional_args
    let is_prime ?opt x = (* randomly try up to opt.max_iters to find a divisor *)  
end