Re: Primes in SML/NJ

Aaron Hawley wrote:
> I'm not good at nor get excited by prime number generation, it was fun to do it in SML/NJ, though.
> 
> (* "Lame" prime number generation in SML/NJ
>  * by Aaron Hawley
>  * Right to Copy is For All
>  *)

Here's my take on a primality tester, based on the Scheme version Oleg
Kiselyov wrote a while back on c.l.scheme.

For a description of the algorithm see:

   http://mathworld.wolfram.com/EratosthenesSieve.html

This is OCaml.  It's also posted at:

   http://www.cs.uvm.edu/~dvanhorn/ocaml/sieve.ml

-d


(*
   Copyright (c) 2003 David Van Horn
   Licensed under the Academic Free License version 2.0

   Eratosthenes Sieve Algorithm
   [email protected]

   This program provides a pure-functional, generic implementation of the
   Eratosthenes sieve.
*)

open List

(*
   We use the obvious encoding of integers as OCaml ints.  A Peano-Church
   representation would be trivial to provide.
*)

type integer = Int of int
let number_two = Int(2)
let number_zero = Int(0)
let is_less_than_two (Int n) = n < 2
let incr (Int n) = Int(n + 1)
let decr (Int n) = Int(n - 1)
let is_number_zero (Int n) = n = 0

(* build a list [2..n] *)
let iota n =
  let rec loop curr counter =
    if is_less_than_two counter then []
    else curr::(loop (incr curr) (decr counter))
  in
  loop number_two n

let sieve lst =
  let rec choose_pivot = function
  | [] -> []
  | car::cdr when is_number_zero car ->
      car::(choose_pivot cdr)
  | car::cdr ->
      car::(choose_pivot (do_sieve car (decr car) cdr))

  and do_sieve step current lst =
    match lst with
    | [] -> []
    | car::cdr ->
	if is_number_zero current
	then number_zero::(do_sieve step (decr step) cdr)
	else car::(do_sieve step (decr current) cdr)
  in
  choose_pivot lst

let is_prime n =
  match rev (sieve (iota n)) with
    x::_ -> not (is_number_zero x)