乐正

Actions speak louder than words.

Sicp-ex1-27

问题

证明脚注47中列出的Carmichael数确实能骗过费马检查。也就是说,写一个过程,它以整数 $n$为参数,对每个$a<n$检查$a^n$是否与$a$模$n$同余。用你的过程去检查前面给出的那 些Carmichael数。

解答

练习1.27 (ex1-27.scm) download
1
2
3
4
5
6
7
8
9
10
(define (carmichael-test? a n)
  (= (expmod a n n) a))

(define (carmichael-prime? n)
  (define (carmichael-prime-iter a)
    (cond ((= a 0) true)
          ((carmichael-test? a n) (carmichael-prime-iter (- a 1)))
          (else false)))

  (carmichael-prime-iter (- n 1)))

测试

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
(carmichael-prime? 561)
;Value: #t

(carmichael-prime? 1105)
;Value: #t

(carmichael-prime? 1729)
;Value: #t

(carmichael-prime? 2465)
;Value: #t

(carmichael-prime? 2821)
;Value: #t

(carmichael-prime? 6601)
;Value: #t

draft

« sicp-ex1-26 sicp-ex1-28 »

Comments