Scheme - 手続きとその生成するプロセス(素数性のテスト(FermatテストをだますCarmichael数))

計算機プログラムの構造と解釈
Gerald Jay Sussman, Julie Sussman
Harold Abelson (原著) 和田 英一 (翻訳)

開発環境

• OS X Mavericks - Apple(OS)
• Emacs (CUI)、BBEdit - Bare Bones Software, Inc. (GUI) (Text Editor)
• Scheme (プログラミング言語)
• Gauche (処理系)

計算機プログラムの構造と解釈(Gerald Jay Sussman(原著)、Julie Sussman(原著)、Harold Abelson(原著)、和田 英一(翻訳)、ピアソンエデュケーション、原書: Structure and Interpretation of Computer Programs (MIT Electrical Engineering and Computer Science)(SICP))の1(手続きによる抽象の構築)、1.2(手続きとその生成するプロセス)、1.2.6(例: 素数性のテスト)、問題 1.27.を解いてみる。

その他参考書籍

• Instructor's Manual to Accompany Structure & Interpretation of Computer Programs
• プログラミングGauche (Kahuaプロジェクト (著), 川合 史朗 (監修), オライリージャパン)

問題 1.27.

コード(BBEdit, Emacs)

sample.scm

#!/usr/bin/env gosh
;; -*- coding: utf-8 -*-

(use srfi-27) ;; fermat-test手続きで使うrandom-integer手続きのため必要

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

(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 (prime? n)
  (= n (smallest-divisor n)))

(define (smallest-divisor n)
  (find-divisor n 2))

(define (find-divisor n test-divisor)
  (cond ((> (square test-divisor) n) n)
        ((divides? test-divisor n) test-divisor)
        (else (find-divisor n (+ test-divisor 1)))))

(define (divides? a b)
  (= (remainder b a) 0))

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

(define (carmichael? n)
  (define (iter a)
    (cond ((= a n) true)
          ((= (remainder (expt a n) n)
              (remainder a n))
           (iter (+ a 1)))
          (else false)))
  (and (iter 0)
       (not (prime? n))))

(define true #t)
(define false #f)

(for-each (lambda (x)
            (if (carmichael? x)
                (print x "はCarmichael数")
                (print x "はCarmichael数ではない")))
          '(2 3 5 7 9 561 1105 1729 2465 2821 6601))

入出力結果(Terminal(gosh), REPL(Read, Eval, Print, Loop))

$ ./sample.scm
2はCarmichael数ではない
3はCarmichael数ではない
5はCarmichael数ではない
7はCarmichael数ではない
9はCarmichael数ではない
561はCarmichael数
1105はCarmichael数
1729はCarmichael数
2465はCarmichael数
2821はCarmichael数
6601はCarmichael数
$