--- a/euler.asd Sat Mar 04 02:50:52 2017 +0000
+++ b/euler.asd Sat Mar 04 02:51:40 2017 +0000
@@ -10,18 +10,17 @@
:depends-on (
+ :anaphora
+ :cl-strings
:fiveam
:iterate
:local-time
:losh
- :cl-strings
- :anaphora
)
:serial t
- :components (
- (:module "vendor" :serial t
+ :components ((:module "vendor" :serial t
:components ((:file "quickutils-package")
(:file "quickutils")))
(:file "package")
--- a/src/primes.lisp Sat Mar 04 02:50:52 2017 +0000
+++ b/src/primes.lisp Sat Mar 04 02:51:40 2017 +0000
@@ -1,11 +1,5 @@
(in-package :euler)
-(define-constant carmichael-numbers ; from oeis
- '(561 1105 1729 2465 2821 6601 8911 10585 15841 29341 41041 46657 52633
- 62745 63973 75361 101101 115921 126217 162401 172081 188461 252601 278545
- 294409 314821 334153 340561 399001 410041 449065 488881 512461)
- :test #'equal)
-
(defun prime-factorization (n)
"Return the prime factors of `n`."
;; from http://www.geeksforgeeks.org/print-all-prime-factors-of-a-given-number/
@@ -13,10 +7,11 @@
(iterate (while (evenp n)) ; handle 2, the only even prime factor
(push 2 result)
(setf n (/ n 2)))
- (loop :for i :from 3 :to (sqrt n) :by 2 ; handle odd (prime) divisors
- :do (iterate (while (dividesp n i))
- (push i result)
- (setf n (/ n i))))
+ (iterate
+ (for i :from 3 :to (sqrt n) :by 2) ; handle odd (prime) divisors
+ (iterate (while (dividesp n i))
+ (push i result)
+ (setf n (/ n i))))
(when (> n 2) ; final check in case we ended up with a prime
(push n result))
(nreverse result)))
@@ -59,22 +54,6 @@
(recur base exp 1)))
-(defun fermat-prime-p (n &optional (tests 10))
- "Return whether `n` might be prime.
-
- Checks `tests` times.
-
- If `t` is returned, `n` might be prime. If `nil` is returned it is definitely
- composite.
-
- "
- (flet ((fermat-check (a)
- (= (expmod a n n) a)))
- (loop :repeat tests
- :when (not (fermat-check (random-range-exclusive 0 n)))
- :do (return nil)
- :finally (return t))))
-
(defun factor-out (n factor)
"Factor the all the `factor`s out of `n`.
@@ -85,10 +64,10 @@
where `d` is no longer divisible by `n`, and returns `e` and `d`.
"
- (loop :for d = n :then (/ d factor)
- :for e = 0 :then (1+ e)
- :while (dividesp d factor)
- :finally (return (values e d))))
+ (iterate (for d :initially n :then (/ d factor))
+ (for e :initially 0 :then (1+ e))
+ (while (dividesp d factor))
+ (finally (return (values e d)))))
(defun miller-rabin-prime-p (n &optional (k 11))
"Return whether `n` might be prime.
@@ -107,13 +86,13 @@
(flet ((strong-liar-p (a)
(let ((x (expmod a d n)))
(or (= x 1)
- (loop :repeat r
- :for y = x :then (expmod y 2 n)
- :when (= y (1- n))
- :do (return t))))))
- (loop :repeat k
- :for a = (random-range-exclusive 1 (1- n))
- :always (strong-liar-p a)))))))
+ (iterate (repeat r)
+ (for y :initially x :then (expmod y 2 n))
+ (when (= y (1- n))
+ (return t)))))))
+ (iterate (repeat k)
+ (for a = (random-range-exclusive 1 (1- n)))
+ (always (strong-liar-p a))))))))
(defun brute-force-prime-p (n)
"Return (slowly) whether `n` is prime."
@@ -121,10 +100,10 @@
((or (= n 0) (= n 1)) nil)
((= n 2) t)
((evenp n) nil)
- (t (loop :for divisor :from 3 :to (sqrt n)
- :when (dividesp n divisor)
- :do (return nil)
- :finally (return t)))))
+ (t (iterate (for divisor :from 3 :to (sqrt n))
+ (when (dividesp n divisor)
+ (return nil))
+ (finally (return t))))))
(defun primep (n)
@@ -195,13 +174,13 @@
"Return the `n`th prime number."
(if (= n 1)
2
- (loop :with seen = 1
- :for i :from 3 :by 2
- :when (primep i)
- :do (progn
- (incf seen)
- (when (= seen n)
- (return i))))))
+ (iterate
+ (with seen = 1)
+ (for i :from 3 :by 2)
+ (when (primep i)
+ (incf seen)
+ (when (= seen n)
+ (return i))))))
(defun woodall (n)