I've got 99 Problems - and OCaml is all of them (Arithmetic)

Problemset

Determine whether a given integer number is prime. (medium)

let is_prime n =
if n < 2 then false else
let rec aux n c =
if c * c > n then true elseif n % c = 0 then false else
aux n (c+1) in
aux n 2;;

Determine the greatest common divisor of two positive integer numbers. (medium)

let rec gcd a b =
if b = 0 then a else gcd b (a % b);;

Determine whether two positive integer numbers are coprime. (easy)

let co_prime a b = if gcd a b = 1 then true else false;;

Calculate Euler's totient function φ(m). (medium)

Skipped. See improved version.

Determine the prime factors of a given positive integer. (medium)

let rec factors ?(c=2) n =
if n % c = 0 then c :: factors (n / c) ~c else
if c * c > n then if n = 1 then [] else [n] else
factors n ~c:(c+1);;

Determine the prime factors of a given positive integer (2). (medium)

let factors n =
let rec aux cur cnt n =
if n mod cur = 0 then aux cur (cnt+1) (n/cur) else
if cnt > 0 then (cur, cnt) :: aux (cur+1) 0 n else
if cur * cur > n then if n = 1 then [] else [(n, 1)] else
aux (cur+1) 0 n in
aux 2 0 n;;

Note: Complexity = sqrt(N)

Calculate Euler's totient function φ(m) (improved). (medium)

let phi_improved n =
let pf = factors n in
List.fold ~init:1 ~f:(fun old (n, c) -> old * ((n-1) * Int.of_float((Float.of_int n) ** (Float.of_int (c - 1))))) pf;;

Compare the two methods of calculating Euler's totient function. (easy)

I used their implementation as benchmark for slow one.

let timeit f a =

let start = Unix.gettimeofday () in

let res = f a in

let e = Unix.gettimeofday () in

e -. start;;

A list of prime numbers. (easy)

let all_primes s f =

List.filter ~f:is_prime (range s f);;

Goldbach's conjecture. (medium)

let goldbach num =

let rec aux n num =

if is_prime n && is_prime (num-n) then (n, (num-n)) else aux (n+1) num in

aux 2 num;;

A list of Goldbach compositions. (medium)

let rec goldbach_list s f =

if s mod 2 <> 0 then goldbach_list (s+1) f else

if s > f then [] else

(s, goldbach s) :: goldbach_list (s+1) f;;