(* Programmieraufgabe P-40 (sieb.ml)				*)
(* Leonhard Fellermayr								*)
(* Mat.Nr. 22128130XXXX								*)

(* ===================================================================
   erzeuge_liste : Erzeuge eine Liste der Zahlen von c bis n.
   =================================================================== *)

let rec erzeuge_liste c n =
  if (c <= n) then c::(erzeuge_liste (c+1) n)
  else [];;

(* ===================================================================
   streiche_vielfache : Streicht Vielfache des Werts wert aus der
   Liste liste und gibt diese Liste anschlie§end "bereinigt" zurŸck.
   =================================================================== *)

let rec streiche_vielfache wert liste = match liste with
    (x::xs) -> if (x mod wert == 0) && (x <> wert) then
                  streiche_vielfache wert xs
               else
                  x::(streiche_vielfache wert xs)
  | [] -> [];;

(* ===================================================================
   find_successor : Finde (šrtlichen) Nachfolger des Elements ele i.d.
   Liste l und gib ihn zurŸck. Andernfalls gib -1 zurŸck (Fehlercode).
   =================================================================== *)

let rec find_successor ele l = match l with
  (x::y::xs) -> if (x == ele) then y else find_successor ele (y::xs)
  |_ -> -1;;

(* ===================================================================
   process_list : Liste von Zahlen [2..n] durchackern und jeweils
   Vielfache v entfernen (Sieb des Eratosthenes).
   =================================================================== *)

let rec process_list l v = match v with
   -1 -> l
  | _ -> process_list (streiche_vielfache v l) (find_successor v l);;

(* ===================================================================
   primzahl : Benutzerfunktion
   =================================================================== *)

let primzahl n = process_list (streiche_vielfache 2 (erzeuge_liste 2 n)) 3;;

(* EOF *)