Sieve of Eratosthenes: Difference between revisions
m
add consistency to examples
m (add consistency to examples) |
|||
Line 11,853:
===Functional===
<lang ocaml>(* first define some iterators *)
(* val fold_iter : ('a -> int -> 'a) -> 'a -> int -> int -> 'a
(* val fold_step : ('a -> int -> 'a) -> 'a -> int -> int -> int -> 'a
(* remove a given value from a list *)
(* val remove : 'a list -> 'a -> 'a list
(* the main function *)
</lang>
▲val primes : int -> int list = <fun>
in the top-level:
<lang ocaml># primes 200 ;;
- : int list =
[2; 3; 5; 7; 11; 13; 17; 19; 23; 29; 31; 37; 41; 43; 47; 53; 59; 61; 67; 71;
Line 11,906:
This uses zero to denote struck-out numbers. It is slightly inefficient as it strikes-out multiples above p rather than p<sup>2</sup>
<lang ocaml>
| [] -> []
| h :: t ->
if k = 0 then 0 :: strike_nth (n-1) n t
else h :: strike_nth (k-1) n t
(* val strike_nth : int -> int -> int list -> int list
let limit = truncate(sqrt(float n)) in
let rec range a b = if a > b then [] else a :: range (a+1) b in
Line 11,921:
| h :: t -> if h > limit then List.filter ((<) 0) l else
h :: sieve_primes (strike_nth (h-1) h t) in
sieve_primes (range 2 n)
(* val primes : int -> int list
</lang>
# primes 200;;▼
in the top-level:
▲<lang ocaml># primes 200;;
- : int list =
[2; 3; 5; 7; 11; 13; 17; 19; 23; 29; 31; 37; 41; 43; 47; 53; 59; 61; 67; 71;
| |||