リスト修行 約数のリストを求める

Scheme

久しぶりにリスト修行をしよう。

約数

今回のテーマは約数にした。

wikipediaによると、

約数 - Wikipedia

50 の正の約数は 1, 2, 5, 10, 25, 50 の 6 個

おぉ、リスト向き!!と思ったので、修行してみる。

再帰で

再帰で解いてみる。

(define (divisor n)
  (define (iter m)
    (cond ((> m n) '())
          ((= (modulo n m) 0)
           (cons m
                 (iter (+ m 1))))
          (else
             (iter (+ m 1)))))
    (iter 1))
  • 1があって、割り切れるので置いとく。
  • 2があって、割り切れるので置いとく。
  • 3があって、割り切れないので飛ばす。
  • ...
  • 51があったら'()
  • ダダァッとcons。

実行〜

(divisor 50) ; (1 2 5 10 25 50)

おぉ、でた!!

反復で

じゃ、反復で

(define (divisor n)
  (define (iter m l)
    (cond ((= m 0) l)
          ((= (modulo n m) 0)
           (iter (- m 1) (cons m l)))
          (else
            (iter (- m 1) l))))
  (iter n '()))

(divisor 50) ; (1 2 5 10 25 50)


ダダァッとconsする必要が無くなった。

srfi-1を使う。

次はsrfi-1を使ってやってみる。

(define (divisor n)
  (filter (lambda (m)
            (= (modulo n m) 0))
  (iota n 1)))

(divisor 50) ; (1 2 5 10 25 50)

すっきり書けた。ifすらいらない。

課題

でも、1から50まで全部走査する必要は無い気がする。高速化するにはどうすればいいのか考えてみる。