-
Notifications
You must be signed in to change notification settings - Fork 1
/
216.ss
41 lines (34 loc) · 1012 Bytes
/
216.ss
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
; Project Euler
; Problem 216
; Look at the primality of numbers of the form
; t(n) = 2 * n^2 - 1, n > 1
(define (t n)
(- (* 2 (square n)) 1))
(define (prob-216 n-max)
(define (count-primes n-current n-max count)
(if (> n-current n-max)
count
(if (is-prime? (t n-current))
(count-primes (+ n-current 1) n-max (+ count 1))
(count-primes (+ n-current 1) n-max count))))
(count-primes 2 n-max 0))
(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 (fermat-test n)
(define (try-it a)
(= (expmod a n n) a))
(try-it (+ 1 (random (- n 1)))))
(define (fast-prime? n times)
(cond ((= times 0) true)
((fermat-test n) (fast-prime? n (- times 1)))
(else false)))
(define (is-prime? n)
(fast-prime? n 10))