62 lines
1.4 KiB
Plaintext
62 lines
1.4 KiB
Plaintext
(defn random [n]
|
|
(math/floor (* n (math/random))))
|
|
|
|
(defn square [n]
|
|
(* n n))
|
|
|
|
(defn divides? [a b]
|
|
(= (mod b a) 0))
|
|
|
|
(defn expmod [base exp m]
|
|
(cond
|
|
(= exp 0) 1
|
|
(even? exp) (mod (square (expmod base (/ exp 2) m)) m)
|
|
(mod (* base (expmod base (- exp 1) m)) m)))
|
|
|
|
(defn fast-expt [b n]
|
|
(defn expt-iter [b n s]
|
|
(cond
|
|
(= n 0) s
|
|
(even? n) (square (expt-iter b (/ n 2) s))
|
|
(* b (expt-iter b (- n 1) s))))
|
|
(expt-iter b n 1))
|
|
|
|
(defn expmod-n [base exp m]
|
|
(mod (fast-expt base exp) m))
|
|
|
|
(print (expmod 10 11 11))
|
|
(print (expmod-n 10 11 11))
|
|
|
|
(defn fermat-test [n]
|
|
(defn try-it [a]
|
|
(= (expmod a n n) a))
|
|
(try-it (+ 1 (random (- n 1)))))
|
|
|
|
(defn fast-prime? [n times]
|
|
(cond
|
|
(= times 0) true
|
|
(fermat-test n) (fast-prime? n (- times 1))
|
|
false))
|
|
|
|
(defn search-for-primes [start count]
|
|
(defn report-time [n elapsed-time]
|
|
(printf "%d,%f" n (* elapsed-time 1000000.0)))
|
|
(defn start-prime-test [n start-time]
|
|
(if (fast-prime? n 7)
|
|
(do
|
|
(report-time n (- (os/clock :cputime) start-time))
|
|
true)
|
|
false))
|
|
(defn times-prime-test [n]
|
|
(start-prime-test n (os/clock :cputime)))
|
|
(defn iter [test n]
|
|
(cond
|
|
(= n 0) 0
|
|
(times-prime-test test) (iter (+ test 2) (- n 1))
|
|
(iter (+ test 2) n)))
|
|
(cond
|
|
(= 0 (mod start 2)) (iter (+ start 1) count)
|
|
(iter start count)))
|
|
|
|
#(search-for-primes 1000 1000000)
|