another-prime-test

secje posted @ 2010年5月10日 11:18 in sicp , 1244 阅读

 

(define (square x) (* x x))
(define (fast-prime? n)
  (define (expmod base exp m)
    (cond ((= exp 0) 1)
          ((even? exp)
           (remainder (square (expmod base (/ exp 2) m))
                      m))
          (else
           (remainder (* (remainder base m) (expmod base (- exp 1) m))
                    m))))
  (define (fermat-test a)
    (= (expmod a n n) a))
  (define (test a)
    (cond ((= a n) #t)
          ((fermat-test a) (fermat-test (+ a 1)))
          (else #f)))
  (cond ((= n 1) #f)
        ((= n 2) #t)
        (else (test 1))))

为了在PLT下玩,自己改了下,代码量不够的劣势就显示出来了,如此简单的东东,我做了半天= =

 看了网上的答案,自己改了下

 

(define (square x) (* x x))
(define (fast-prime? n)
  (define (expmod base exp m)
    (cond ((= exp 0) 1)
          ((even? exp)
           (remainder (square (expmod base (/ exp 2) m))
                      m))
          (else
           (remainder (* (remainder base m) (expmod base (- exp 1) m))
                    m))))
  (define (fermat-test a)
    (= (expmod a n n) a))
  (define (test a)
    (cond ((= a 0) #t)
          ((fermat-test a) (fermat-test (- a 1)))
          (else #f)))
  (test (- n 1)))

 

 

 


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter