SICP#3まとめ　vol.2 - snow-bellの日記

次に除数の探索

(define (smallest-divisor n)
 (find-divisor n 2 ))

(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)))))

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

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

ココで思ったんですけどまず

((> (square test-divisor) n) n)

このコードがなくても問題なさそうな気がしました

このコードを読むと

　smallest-divisorをnと定義する
　find-divisor nは2とする

　find-divisor nはtest-divisorと定義する
　test-divisorの二乗がnより大きいかnの場合
　test-divisorをnで割った時にtest-divisorで割り切れる?場合
　→find-divisor n
　その他はtest-divisorに1を足してfind-divisor nを再帰

　aをbで割る事が出来る?と定義する
　a/bの剰余=0
　
  nを素数?と定義する
  smallest-divisor n = n

こんな感じですよね

(define (smallest-divisor n)
 (find-divisor n 2 ))

素数は1は含まれないので2からスタートするのでココでは
find-divisor nを2と定義してます

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

(define (prime? n)
 (= n (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)))))

ココが理解出来るような出来ないような。。。
そこで実際に数字を代入して考えていきたいと思います

コード1

(define (smallest-divisor n)
 (find-divisor n 2 ))

(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)))))

コード2

(define (smallest-divisor n)
 (find-divisor n 2 ))

(define (find-divisor n test-divisor)
 (cond  (( divides? test-divisor n) test-divisor)
       ( else (find-divisor n (+ test-divisor 1)))))

コード1、コード2に(smallest-divisor 13)を代入したいと思います
まずコード1から

test-divisorが2の時
( else (find-divisor n (+ test-divisor 1)))となり
test-divisorが3の時
( else (find-divisor n (+ test-divisor 1)))となる
((> (square test-divisor) n) n)となり
4を二乗した16の方が13より大きくなるのでsmallest-divisor 13

では次にコード2

(( divides? test-divisor n) test-divisor)で
test-divisorが2の時13を2で割り切れないので
( else (find-divisor n (+ test-divisor 1)))
test-divisorが3の時13を3で割り切れないので
( else (find-divisor n (+ test-divisor 1)))
test-divisorが4の時13を4で割り切れないので
( else (find-divisor n (+ test-divisor 1)))
test-divisorが5の時13を5で割り切れないので
( else (find-divisor n (+ test-divisor 1)))
test-divisorが6の時13を6で割り切れないので
( else (find-divisor n (+ test-divisor 1)))
test-divisorが7の時13を7で割り切れないので
( else (find-divisor n (+ test-divisor 1)))
test-divisorが8の時13を8で割り切れないので
( eles (find-divisor n (+ test-divisor 1)))
test-divisorが9の時13を9で割り切れないので
( else (find-divisor n (+ test-divisor 1)))
test-divisorが10の時13を10で割り切れないので
( else (find-divisor n (+ test-divisor 1)))
test-divisorが11の時13を11で割り切れないので
( else (find-divisor n (+ test-divisor 1)))
test-divisorが12の時13を12で割り切れないので
( else (find-divisor n (+ test-divisor 1)))
test-divisorが13の時13を13で割り切れるので
smallest-divisor 13

処理結果は同じですけど処理の内容が全然違いますね
じゃあ次はコード1、コード2に(smallest-divisor 35)を代入したいと思います
まずコード1から

test-divisorが2の時
( else (find-divisor n (+ test-divisor 1)))となり
test-divisorが3の時
( else (find-divisor n (+ test-divisor 1)))となる
test-divisorが4の時
test-divisorが4の時
( else (find-divisor n (+ test-divisor 1)))となり
test-divisorが5の時
((> (square test-divisor) n) n)には当てはまらないけど
(( divides? test-divisor n) test-divisor)には当てはまります
35は5で割り切れます
なのでsmallest-divisor 5

では次にコード2

(( divides? test-divisor n) test-divisor)で
test-divisorが2の時35を2で割り切れないので
( else (find-divisor n (+ test-divisor 1)))
test-divisorが3の時35を3で割り切れないので
( else (find-divisor n (+ test-divisor 1)))
test-divisorが4の時35を4で割り切れないので
( else (find-divisor n (+ test-divisor 1)))
test-divisorが5の時35を5で割り切れるので
smallest-divisor 5

今度は処理あんまり変わらないですよね
うーん・・・
じゃあやっぱり

((> (square test-divisor) n) n)

このコードには何の意味があるのだろうか
処理速度かなぁ??
ちなみにこのアルゴリズムや処理に関しては某チャットにて教えて頂きました
ご本人の許可があったら敬意や感謝を込めてお名前を公表したいです♪
書いてるうちい長くなりすぎて公開が遅くなっちゃったなぁ(ﾉД｀ﾟ)ﾟ。