SICP § 1.2.6 素数性のテスト（その２）

あんまり数学にかかずらわって本来の目的が遂行されないのもアレなので、
例のmodulo演算の展開は「そういうもの」として進むことにしました。
つーわけでコレです。

;ある数のべき乗を法とする剰余を求める関数
(define (expmod base exp m)
  (cond ((= exp 0) 1)
        ((even? exp)
         (remainder (square (expmod base (/ exp 2) m))
                    m))
        (else
         (remainder (* base (expmod base (- exp 1) m))
                    m))))
;おまけ
;実行するときに定義されていないと動かないので一応。
(define (square x)
  (* x x))

で、次に

;Fermatテスト関数
(define (fermat-test n)
  (define (try-it a)
    (= (expmod a n n) a))
  (try-it (+ 1 (random-integer (- n 1)))))

更に、

;Fermatテスト関数を指定回数実行する関数
(define (fast-prime? n times)
  (cond ((= times 0) #t)
        ((fermat-test n) (fast-prime? n (- times 1)))
        (else #f)))

実行結果はコレ。

gosh> (map (lambda (x) (cons x (fast-prime? x 10))) (iota 100 2))

((2 . #t) (3 . #t) (4 . #f) (5 . #t) (6 . #t) (7 . #t) (8 . #f) (9 . #f) (10 . #f)

(11 . #t) (12 . #f) (13 . #t) (14 . #f) (15 . #f) (16 . #f) (17 . #t) (18 . #f) (19 . #t) (20 . #f) 

(21 . #f) (22 . #f) (23 . #t) (24 . #f) (25 . #f) (26 . #f) (27 . #f) (28 . #f) (29 . #t) (30 . #f) 

(31 . #t) (32 . #f) (33 . #f) (34 . #f) (35 . #f) (36 . #f) (37 . #t) (38 . #f) (39 . #f) (40 . #f) 

(41 . #t) (42 . #f) (43 . #t) (44 . #f) (45 . #f) (46 . #f) (47 . #t) (48 . #f) (49 . #f) (50 . #f) 

(51 . #f) (52 . #f) (53 . #t) (54 . #f) (55 . #f) (56 . #f) (57 . #f) (58 . #f) (59 . #t) (60 . #f) 

(61 . #t) (62 . #f) (63 . #f) (64 . #f) (65 . #f) (66 . #f) (67 . #t) (68 . #f) (69 . #f) (70 . #f) 

(71 . #t) (72 . #f) (73 . #t) (74 . #f) (75 . #f) (76 . #f) (77 . #f) (78 . #f) (79 . #t) (80 . #f) 

(81 . #f) (82 . #f) (83 . #t) (84 . #f) (85 . #f) (86 . #f) (87 . #f) (88 . #f) (89 . #t) (90 . #f) 

(91 . #f) (92 . #f) (93 . #f) (94 . #f) (95 . #f) (96 . #f) (97 . #t) (98 . #f) (99 . #f) (100 . #f) (101 . #t))

gosh> 

・・・消化不良ですよ。

−