prime.ml

(* s から e までの整数のリストを作成する *)
let rec makeListSub s e lst =
  match e - s with
    0 -> e::lst
  | _ -> makeListSub s (e-1) (e::lst)

let makeList s e = 
  if s < e 
  then makeListSub s e []
  else makeListSub e s []
  
(* リストの最初の要素の倍数をリストから取り除いたものを返す *)
let rec updatePrimeSub x lst =
  match lst with
    [] -> []
  | first :: rest -> if first mod x = 0
		     then updatePrimeSub x rest
		     else first :: updatePrimeSub x rest

let updatePrime lst =
  match lst with 
    [] -> []
  | first :: rest -> updatePrimeSub first rest

(* 指定された値がリストに含まれるかどうかを調べる *)
let rec searchList n lst =
  match lst with
    [] -> false
  | first :: rest -> if first = n then true else searchList n rest


(* 指定された数が素数かどうか判定する *)
let rec checkPrime n lst =
  match lst with
    [] -> false
  | first :: [] -> if first = n 
		   then true
		   else false
  | llst -> if searchList n llst
	    then checkPrime n (updatePrime llst)
	    else false

let rec isPrime n = checkPrime n (makeList 2 n)


(* 指定された数までの素数をリストにする *)
let rec listPrimeSub n lst =
  match n with
    0 -> lst
  | m -> if isPrime m
	 then listPrimeSub (m-1) (m::lst)
	 else listPrimeSub (m-1) lst

let listPrime n = listPrimeSub n []

prime_new.ml

(* == 素数を求める == *)

(*
  start が lst に含まれる数で割り切れるかどうか調べる 
  いずれかの値で割り切れれば false, どれでも割り切れなかったら true 
 *)
let rec isPrime lst num =
  match lst with
    [] -> true
  | first :: r -> 
     if num mod first = 0 
     then false 
     else isPrime r num

(* 指定された値よりも大きな、リストに含まれる数で割り切れない最初の数を返す *)
let rec nextPrime lst start =
  match lst with
    [] -> 2  (* 最初の素数は2 *)
  | _ -> if isPrime lst start
	 then start
	 else nextPrime lst (start + 1)

(* リストの末尾に値をひとつ追加する *)
let appendOne lst v = List.rev (v :: List.rev lst)

let rec getPrime lst now n =
  let next = nextPrime lst (now + 1) in
  let appended = appendOne lst next in
  let leftSize = n - 1 in
  print_int next;
  print_string " ";
  if n mod 15 = 0 then print_newline() else ();
  if leftSize <= 0 
  then appended
  else getPrime appended next leftSize


(* 素数を小さい順にn個求める *)
let listPrime n = getPrime [] 0 n; 
		  print_newline ()