Решение упражнения 1.27 из SICP

12 October, 2007 (20:41) | Решения упражнений

Код процедуры проверки приведен ниже. Процедура называется (test-all) и принимает один параметр – число для проверки на простоту.

(define (square x) 
  (* x x))
(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 (test a n) 
  (= (expmod a n n) a))
(define (test-all n) 
  (test-all-from n 1))
(define (test-all-from n start) 
  (if (< start n) 
        (if (test start n) 
            (test-all-from n (+ start 1)) 
            false) 
        true))

Запустим сначала эту процедуру на нескольких числах:

> (test-all 1009) 
#t 
> (test-all 1008) 
#f 
> (test-all 1000003) 
#t

Как видим, для простых чисел возвращается истина, а для составных – ложь. Все как и следовало ожидать.

Теперь проверим несколько первых чисел Кармайкла (561, 1105, 1729, 2465, 2821 и 6601):

> (test-all 561) 
#t 
> (test-all 1105) 
#t 
> (test-all 1729) 
#t 
> (test-all 2465) 
#t 
> (test-all 2821) 
#t 
> (test-all 6601) 
#t 

На всех этих числах тест Ферма проходит, но в то же время они составные.

Comments

Comment from Irv
Date: January 4, 2016, 9:14 pm

(define (square x) (* x x)) 

(define (expmod b n m) 
  (cond ((= n 0) 1) 
        ((even? n)
         (remainder (square (expmod b (/ n 2) m)) m))
        (else 
         (remainder (* b (expmod b (- n 1) m)) m))))

(define (carmichael-test n)
  (define (good? a)
    (= (expmod a n n) a))
  (define (iter i)
    (define (report-fail) 
      (display n)
      (display " failed the Carmichael test with an argument of ")
      (display i)
      (newline))
    (define (report-ok) 
      (display n)
      (display " passed the Carmichael test")
      (newline))
    (cond [(> n i)           
           (if (good? i) 
               (iter (+ 1 i))
               (report-fail))]
          [else (report-ok)]))
  (iter 1))

(carmichael-test 561)
(carmichael-test 1105)
(carmichael-test 42)

(define (probably-prime? n) 
  (define (iter times)
    (define (test) 
      (define (try a) 
        (= (expmod a n n) a))
      (try (random (+ 1 (- n 1)))))
    (cond ((= times 0) true) 
          ((test) (iter (- times 1))) 
          (else false)))
  (iter 100))

(define (true-prime? n)
  (define (next x)
    (if (= x 2)
        3
        (+ x 2)))
  (define (try x)
    (if (> (square x) n)
        n
        (if (= (remainder n x) 0)
            x
            (try (next x)))))
  (= (try 2) n))

(define (find-carmichael-numbers limit)
  (define (iter i)
    (define (report)
      (display i)
      (newline))
    (cond [(> limit i)
           (cond [(probably-prime? i)
                  (cond [(not (true-prime? i)) (report)])])
           (iter (+ i 1))]))
  (iter 2))

(find-carmichael-numbers 100000)

Write a comment