本文

1.2.6 例:素数性のテスト

Fermat テスト : ある数が素数か否かを確率的に求める。

テストに失敗すれば素数ではなく、テストに成功すれば高い確率で素数となる。更にテストを繰り返すと正確性が上がっていく。

このようなテストの存在が確率的アルゴリズムとして知られるようになった。

問題解答

問1.21
本のプログラムを写経して実行するだけ。

gosh> (smallest-divisor 199)
199
gosh> (smallest-divisor 1999)
1999
gosh> (smallest-divisor 19999)
7
gosh>

問1.22
gauche には runtime が無いようなので、まずはそれを解決。

prime? などは本をそのまま流用して、search-for-primes はこのような感じ。

(define (search-for-primes n)
  (define (search-for-primes-iter i k)
    (cond ((= k 0))
          ((prime? i)
           (display i)
           (newline)
           (search-for-primes-iter (+ i 2) (- k 1)))
          (else (search-for-primes-iter (+ i 2) k))))
                                
  (search-for-primes-iter n 3))

入力された値の偶奇判断とかモロモロ盛り込もうとするともっと複雑になってしまいそう。
あと、Meadow 上で gosh を走らせてコードを実行すると Stack Trace がきちんと表示されなかったり、ステップ実行できなかったりしてエラーが起きたときの対応が辛い。もっとちゃんとした環境を作らないと効率が悪すぎる。