練習問題 6.14.1
6.5.2で定義した is_prime は、n が素数か判定するのに、n-1 から順に 2 までのすべての数で割り切れるかどうか試していますが、これはあまり効率がよいとはいえません。以下のそれぞれの方法で、3000番目の素数の計算が速くなるかどうか試してみなさい。
- 割る数として、小さい数のほうから試していく
練習問題 6.14 は、4つの小問があるので、ひとつずつ解いていく。
これがひとつめの問題。
解答
type intseq = Cons of int * (int -> intseq);;
(* n番目の要素を取り出す関数 *)
let rec nthseq n (Cons(x, f)) =
if n = 1 then x
else nthseq (n-1) (f x);;
(* 素数かどうかを調べる。小さい数から順に *)
let is_prime1 x =
let rec is_divisible_from_2_to n =
if n = x then false
else
(n > 1) && ((x mod n = 0) || is_divisible_from_2_to (n+1))
in
not (is_divisible_from_2_to 2);;
(* 素数の無限列 *)
let rec prime_seq x =
if is_prime1 (x+1)
then Cons(x+1, prime_seq)
else prime_seq (x+1);;
(* 素数の無限列をつくる *)
let prime = prime_seq 1;;
let test1 = nthseq 10 prime = 29;;
let test2 = nthseq 3000 prime = 27449;; (* 3秒くらい *)