Scheme 代入の練習 (素数)

Scheme

私は、Schemeで代入を使うのが苦手である。
そこで、次のような練習問題を解いてみる。

問題1：10000以上で、２番目に小さい素数を求めよ。
問題2：10000以上で、ｎ番目に小さい素数を求めよ。
準備
(define (square x)
  (* x x))

(define (divides? a b)
  (= (remainder b a) 0))

(define (smallest-divisor n)
  (define (find-divisor n test-divisor)
    (cond ((> (square test-divisor) n) n)
          ((divides? test-divisor n) test-divisor)
          (else (find-divisor n (+ test-divisor 1)))))
  (find-divisor n 2))

(define (prime? n)
  (= (smallest-divisor n) n))

prime?は入力が素数であるかどうか判定する。

(prime? 7)
=> #t

(prime? 8)
=> #f


10000以上で、素数がどのような分布かは、それほど自明ではない。
この問題には、代入を使う方が良いだろう。

http://nibosiiwasi.hatenablog.com/entry/2016/08/11/170848
これと同じような感じで、コードを書いていく。

（create-prime-class-beta には欠陥がある。修正版create-prime-class も書いた。）

欠陥あり！
(define (create-prime-class-beta start)
  (define (prime-number-count start prime-list counter the-number)
    (define (next)
      (begin
        (if (prime? the-number)
          (begin
            (set! prime-list (cons the-number prime-list))
            (set! counter (+ counter 1))))
        (set! the-number (+ the-number 1))))
    (define (search-forward n)
      (begin
        (while (< counter n)
          (next))
        (car prime-list)))
    
    (define (dispatch m)
      (cond ((eq? m 'start) start)
            ((eq? m 'prime-list) prime-list)
            ((eq? m 'counter) counter)
            ((eq? m 'the-number) the-number)
            ((eq? m 's-f) search-forward)))
    dispatch)
  (prime-number-count start '() 0 start))

create-prime-class-beta は次のような動作をする。

;10000をスタートとする
(define prime-over-10000
  (create-prime-class-beta 10000))
=> prime-over-10000

;2番目の素数を求める
((prime-over-10000 's-f) 2)
=> 10009

;素数のリスト
(prime-over-10000 'prime-list)
=> (10009 10007)

ここまでは、期待どおりだが、

;5番目の素数を求める
((prime-over-10000 's-f) 5)
=> 10061

;素数のリスト
(prime-over-10000 'prime-list)
=> (10061 10039 10037 10009 10007)

;2番目の素数を求めようとするが、
;素数のリストの先頭が返ってくる。間違った答え！
((prime-over-10000 's-f) 2)
=> 10061

となる。

解決法は次の２つが考えられる。

  1. 使い方を限定する。(最初に状態変数を)全て初期化してから実行する。
  2. コードを修正する。次のような修正を加えればよい：進みすぎている場合には、過去に調べた素数prime-listを探索する。

コードを修正します。

修正版
(define (create-prime-class start)
  (define (prime-number-count start prime-list counter the-number)
    (define (next)
      (begin
        (if (prime? the-number)
          (begin
            (set! prime-list (cons the-number prime-list))
            (set! counter (+ counter 1))))
        (set! the-number (+ the-number 1))))
    
    ;前(未探索の素数)を探す
    (define (search-forward n)
      (begin
        (while (< counter n)
          (next))
        (car prime-list)))
    
    ;後ろ(既に探索した素数)を探す
    (define (search-back n)
      (define (lookfor pl k)
        (if (= k 0)
          (car pl)
          (lookfor (cdr pl) (- k 1))))
      
      (let ((k (- counter n)))
        (lookfor prime-list k)))
    
    ;n番目の素数を探す。
    (define (find-prime n)
      (if (> counter n)
        (search-back n)
        (search-forward n)))
    
    (define (dispatch m)
      (cond ((eq? m 'start) start)
            ((eq? m 'prime-list) prime-list)
            ((eq? m 'counter) counter)
            ((eq? m 'the-number) the-number)
            ((eq? m 'find-prime) find-prime)))
    dispatch)
  (prime-number-count start '() 0 start))


create-prime-classは、次のように動作する。
これは問題1,問題2 の解答を与える。

;10000をスタートとする
(define prime-over-10000
  (create-prime-class 10000))
=> prime-over-10000

;初期化されている。当たり前ですが、一応確認。
(prime-over-10000 'prime-list)
=> ()

;2番目の素数を求める
((prime-over-10000 'find-prime) 2)
=> 10009

;5番目の素数を求める
((prime-over-10000 'find-prime) 5)
=> 10061

;2番目の素数を求める。今度は正しい答え！
((prime-over-10000 'find-prime) 2)
=> 10009