Primes in SML/NJ

Aaron Hawley <[email protected]>
Newsgroups gmane.org.ballistichelmet.lambda
Message-ID <[email protected]>
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
 *)

(* is 'y' a factor of 'x'? *)
fun is_factor(y, x) = y = 0 orelse (x mod y) = 0;

is_factor(5, 6); (* is 5 a factor of 6 => no (false) *)
is_factor(2, 6); (* is 2 a factor of 6 => yes (true) *)
is_factor(1, 6); (* yes (true) *)
is_factor(0, 6); (* yes (true) *)
is_factor(2, 3); (* no (false) *)

(* is_prime: return true if x is a prime else false *)
fun is_prime(x) =
    let fun prime_test(x, test) = 
	    if test > x then false (* this seems to be only for x=1 *)
	    else if test = x orelse 2 * test > x then true (* optimization *)
	    else if is_factor(test, x) then false
	    else prime_test(x, test + 1)
    in
	prime_test(x, 2) (* test for "primeness" by starting at 2 *)
    end;
is_prime(1); (* false *)
is_prime(2); (* true *)
is_prime(3); (* true *)
is_prime(4); (* false *)
is_prime(5); (* etc. *)
is_prime(6);

(* next_prime: get next prime after n *)
fun next_prime(n) =
    let val next = n + 1
    in
	if is_prime(next) then next
	else next_prime(next)
    end;
next_prime(3); (* next prime after 3 is 5 *)

exception NonPositive;
(* prime: get ith prime *)
fun prime(i) = 
    if i < 1 then raise NonPositive
    else
	(* prime_after: get ith prime after n *)
	let fun prime_after(0, n) = n
	      | prime_after(i, n) =
		prime_after(i - 1, next_prime(n));
	in
	    prime_after(i - 1, 2) (* 2 is the first prime *)
	end;
(*error prime(0); *)
prime(1); (* 1st prime is 2 *)
prime(2); (* 2nd prime is 3 *)
prime(3); (* 3rd prime is 5 *)
prime(4); (* etc. *)
prime(5);
prime(123);

(* primes_before: get list of primes before n *)
fun primes_before(n) = 
    (* primes_span: list of primes between l and n [l, n) *)
    let fun primes_span(l, n) =
	    let val next = next_prime(l)
	    in 
		if next >= n then nil
		else next::primes_span(next, n)
	    end
    in primes_span(1, n)
    end;

primes_before(0); (* primes before 0 => none *)
primes_before(1); (* none *)
primes_before(2); (* none *)
primes_before(3); (* one : [2] *)
primes_before(4); (* two : [2, 3] *)
primes_before(5); (* two : [2, 3] *)

exception NonPositive;
(* primes: get list of i primes *)
fun primes(i) = 
    if i < 1 then raise NonPositive
    else
	(* primes_after: get ith prime after after n *)
	let fun primes_after(0, n) = nil
	      | primes_after(i, n) =
		let val next = next_prime(n)
		in
		    next::primes_after(i - 1, next)
		end
	in
	    primes_after(i, 1) (* get i primes after 1 *)
	end;
(*error primes(0); *)
primes(1);
primes(2);
primes(3);
primes(4);
primes(5);

(* print first 100 primes, one per line *)
map (fn(x) => print(Int.toString(x) ^ "\n")) (primes 100);
lmpx.com only provides a reader for public news (NNTP) servers. It is not affiliated with the servers or forums shown here and is not responsible for the content of articles, which is written by their respective authors.