SICP 1.2 exercises cont. 12

1.27

(define (passes-fermat n)
  (passes-fermat-iter n (- n 1)))

(define (passes-fermat-iter n a)
  (if (> a 1)
      (if (congruent-a-mod-n n a) (passes-fermat-iter n (- a 1)) #f)
    #t))

(define (congruent-a-mod-n n a)
  (= (expmod a n n) (remainder a n)))

guile> (passes-fermat 561)
#t
guile> (passes-fermat 1105)
#t
guile> (passes-fermat 1729)
#t
guile> (passes-fermat 2465)
#t
guile> (passes-fermat 2821)
#t
guile> (passes-fermat 6601)
#t

Comments: I wonder my fermat test implementation was too roundabout.

Advertisements


Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s