3512c67e0138

Problem 7, and add a test suite
[view raw] [browse files]
author Steve Losh <steve@stevelosh.com>
date Sun, 10 Apr 2016 14:30:17 +0000
parents 37bd082d9946
children 20c03264a55e
branches/tags (none)
files Makefile euler.asd euler.lisp package.lisp primes.lisp run-tests.lisp utils.lisp

Changes

diff -r 37bd082d9946 -r 3512c67e0138 Makefile
--- a/Makefile	Sun Apr 10 01:39:44 2016 +0000
+++ b/Makefile	Sun Apr 10 14:30:17 2016 +0000
@@ -1,4 +1,7 @@
-.PHONY: 
+.PHONY: test
 
 quickutils.lisp: make-utilities.lisp
 	sbcl --noinform --load make-utilities.lisp  --eval '(quit)'
+
+test:
+	sbcl --noinform --load run-tests.lisp  --eval '(quit)'
diff -r 37bd082d9946 -r 3512c67e0138 euler.asd
--- a/euler.asd	Sun Apr 10 01:39:44 2016 +0000
+++ b/euler.asd	Sun Apr 10 14:30:17 2016 +0000
@@ -9,6 +9,7 @@
   :version "0.0.1"
 
   :depends-on (#:defstar
+               #:fiveam
                #:optima
                #:trivial-types
                #:cl-arrows
diff -r 37bd082d9946 -r 3512c67e0138 euler.lisp
--- a/euler.lisp	Sun Apr 10 01:39:44 2016 +0000
+++ b/euler.lisp	Sun Apr 10 14:30:17 2016 +0000
@@ -124,3 +124,20 @@
                          :sum i))))
     (abs (- (sum-of-squares 100) ; apparently it wants the absolute value
             (square-of-sum 100)))))
+
+(defun problem-7 ()
+  (nth-prime 10001))
+
+;;;; Tests
+(def-suite :euler)
+(in-suite :euler)
+
+(test p1 (is (= 233168 (problem-1))))
+(test p2 (is (= 4613732 (problem-2))))
+(test p3 (is (= 6857 (problem-3))))
+(test p4 (is (= 906609 (problem-4))))
+(test p5 (is (= 232792560 (problem-5))))
+(test p6 (is (= 25164150 (problem-6))))
+(test p7 (is (= 104743 (problem-7))))
+
+; (run! :euler)
diff -r 37bd082d9946 -r 3512c67e0138 package.lisp
--- a/package.lisp	Sun Apr 10 01:39:44 2016 +0000
+++ b/package.lisp	Sun Apr 10 14:30:17 2016 +0000
@@ -1,7 +1,9 @@
 (defpackage #:euler.utils
   (:use #:cl #:euler.quickutils)
   (:export
+    #:random-exclusive
     #:dividesp))
 
 (defpackage #:euler
-  (:use #:cl #:euler.quickutils #:euler.utils))
+  (:use #:cl #:5am
+        #:euler.quickutils #:euler.utils))
diff -r 37bd082d9946 -r 3512c67e0138 primes.lisp
--- a/primes.lisp	Sun Apr 10 01:39:44 2016 +0000
+++ b/primes.lisp	Sun Apr 10 14:30:17 2016 +0000
@@ -16,4 +16,58 @@
     (nreverse result)))
 
 
+(defun fermat-prime-p (p &optional (tests 10))
+  "Return whether `p` might be prime.
 
+  Checks `tests` times.
+
+  If `t` is returned, `p` might be prime.  If `nil` is returned it is definitely
+  composite.
+
+  "
+  (if (or (zerop p) (= 1 p))
+    nil
+    (flet ((fermat-check (a)
+             (= 1 (mod (expt a (1- p)) p))))
+      (loop :repeat tests
+            :when (not (fermat-check (random-exclusive 0 p)))
+            :do (return nil)
+            :finally (return t)))))
+
+(defun brute-force-prime-p (p)
+  "Return (slowly) whether `p` is prime."
+  (cond
+    ((or (= p 0) (= p 1)) nil)
+    ((= p 2) t)
+    ((evenp p) nil)
+    (t (loop :for divisor :from 3 :to (sqrt p)
+          :when (dividesp p divisor)
+          :do (return nil)
+          :finally (return t)))))
+
+
+(defun primes-below (n)
+  "Return (slowly) the prime numbers less than `n`."
+  (cond
+    ((<= n 2) (list))
+    ((= n 3) (list 2))
+    (t (cons 2 (loop :for i :from 3 :by 2 :below n
+                     :when (brute-force-prime-p i)
+                     :collect i)))))
+
+(defun primes-upto (n)
+  "Return (slowly) the prime numbers less than or equal to `n`."
+  (primes-below (1+ n)))
+
+
+(defun nth-prime (n)
+  "Return (slowly) the `n`th prime number."
+  (if (= n 1)
+    2
+    (loop :with seen = 1
+          :for i :from 3 :by 2
+          :when (brute-force-prime-p i)
+          :do (progn
+                (incf seen)
+                (when (= seen n)
+                  (return i))))))
diff -r 37bd082d9946 -r 3512c67e0138 run-tests.lisp
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/run-tests.lisp	Sun Apr 10 14:30:17 2016 +0000
@@ -0,0 +1,15 @@
+(let ((*standard-output* (make-broadcast-stream)))
+  (ql:quickload "euler"))
+
+
+(defvar *passed* t)
+
+(defun test (spec)
+  (let ((result (5am:run spec)))
+    (5am:explain! result)
+    (when (not (5am:results-status result))
+      (setf *passed* nil))))
+
+(test :euler)
+
+(sb-ext:exit :code (if *passed* 0 1))
diff -r 37bd082d9946 -r 3512c67e0138 utils.lisp
--- a/utils.lisp	Sun Apr 10 01:39:44 2016 +0000
+++ b/utils.lisp	Sun Apr 10 14:30:17 2016 +0000
@@ -1,5 +1,9 @@
 (in-package #:euler.utils)
 
+(defun random-exclusive (min max)
+  "Return an integer in the range (`min`, `max`)."
+  (+ 1 min (random (- max min 1))))
+
 (defun dividesp (n divisor)
   "Return whether `n` is evenly divisible by `divisor`."
   (zerop (mod n divisor)))