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);