2c77c8003d75

`loop` is garbage
[view raw] [browse files]
author Steve Losh <steve@stevelosh.com>
date Sat, 04 Mar 2017 02:51:40 +0000
parents 9105703a2339
children 6dd2cb3e5f27
branches/tags (none)
files euler.asd src/primes.lisp

Changes

--- 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)