Sieve

primes-sieve.md

Here's the prime sieve of eratosthenes implemented in 4 different functional languages.

Which one's your favorite?

OCaml

let rec range s e = if s > e then [] else s :: range (s + 1) e;;

let countprimes n =
  let rec aux count = function
    | x :: xs -> if x * x <= n
      then aux (count+1) (List.filter (fun c -> c mod x != 0) xs)
      else count + (List.length xs)
    | _ -> 0
  in
  aux 0 (range 2 (n + 1))
;;

JSJS

val countPrimes = /\(n: num): num => {
  val aux = /\(count: num, l: list num): num => {
    if hd(l) * hd(l) <= n
    then aux(count + 1, List.filter(/\(x: num): bool => x % hd(l) != 0, l))
    else count + List.length(l);
  };

  aux(0, List.range(2, n+1));
};

Clojure

(defn countprimes [n]
  (loop [c 0 [x & xs] (range 2 (inc n))]
    (if (<= (* x x) n)
      (recur (inc c) (filter #(not= 0 (mod % x)) xs))
      (+ c (count xs)))))

Scala

def countPrimes(n: Int): Int = {
  def aux(count: Int, l: List[Int]): Int = {
    if (l.head * l.head < n) aux(count+1, l.filter(_ % l.head != 0))
    else count + l.length
  }
  aux(0, (2 to n).toList)
}

JSJS and Scala all the way!!
Clojure if I knew it...no range in OCaml :(