# Section 1.2.6 Example: Testing for Primality


```scheme
(if (> 1 2)
    (print "true")
    (print "false"))
```

    "false"



```scheme
(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 n)
  (* n n))
```


```scheme
(define (prime? n)
  (= n (smallest-divisor n)))

(print (prime? 4))
(print (prime? 5))
(print (prime? 13))
```

    #f
    #t
    #t


The order of this procedure is $\Theta(\sqrt{n})$

## The Fermat test

The $\Theta(\log{n})$ primality test is based on a result from number theory known as ***Fermat's Little Theorem***.

### Fermat's Little Theorem - フェルマーの小定理:

If $n$ is prime and $a$ is ***any positive interger*** less than $n$, the $a$ raised to the $n$-th power is congruent to $a$ modulo $n$.

I.e., $a \equiv a^n \pmod{n}$

- $a \equiv a^n$ でなかった場合は、即それは素数でないと判断できる。
- $a \equiv a^n$ だった場合は、素数の可能性があるので、ことなる $a$ でまた探索をする


```scheme
;; base = a
;; exp = 1,...,n
;; m = n
(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))))
```

$
\begin{align}
a^n\bmod{n} = \left\{
\begin{aligned}
\left[ (a^{n/2} \bmod{n})^2 \right] \bmod{n} &\quad \textrm{if $n$ is even} \\
\left[ (a^{n-1} \bmod{n}) \cdot a \right] \bmod{n} &\quad \textrm{overwise}
\end{aligned}
\right.
\end{align}
$


```scheme
(define (fermat-test n)
  (define (try-it a)
    (= (expmod a n n) a))
  (try-it (+ 1 (random (- n 1)))))
```


```scheme
(define (fast-prime? n times)
  (cond 
   ((= times 0) #t)
   ((fermat-test n) (fast-prime? n (- times 1)))
   (else #f)
   )
  )
```


```scheme
(print (fast-prime? 2 10))
(print (fast-prime? 11 10))
(print (fast-prime? 443 10))
(print (fast-prime? 93 10))
```

    #t
    #t
    #t
    #f



```scheme

```

a8d01a61a7142fe8c02a25fe795d78060962bd29
ipynb
Jupyter Notebook
chapter01/sec1.2.6.ipynb
tyohei/sicp2e
733f17f112fb43117b37c663ee1be33afc3794d8
MIT
chapter01/sec1.2.6.ipynb
tyohei/sicp2e
733f17f112fb43117b37c663ee1be33afc3794d8
MIT
chapter01/sec1.2.6.ipynb
tyohei/sicp2e
733f17f112fb43117b37c663ee1be33afc3794d8
MIT
Qwen/Qwen-72B
1. YES
2. YES