Commits

David Jones  committed b42dc8f

added sieve. and boy, the dumb prime test was dumb. it was wrong. comparison on
square root was off by one.

  • Participants
  • Parent commits b90930c

Comments (0)

Files changed (1)

File lisp/basic-math.lisp

   "Super simple prime test.  Not meant for real use, but could be used
 to test better prime tester functions."
   (cond ((<  n 2) nil)
-        ((= 2 n) t)
+        ((= 2 n) 2)
         ((= (mod n 2) 0) (values nil 2))
         (t
          (do ((i 3 (+ 2 i)))
-             ((>= i (sqrt n)) n)
+             ((>= i (+ 1 (sqrt n))) n)
            (when (= (mod n i) 0) 
              (return (values nil i)))))))
 
 
+(defun range (end &key (start 0))
+  "Create an array of integers from START [ 0 ] to END - 1."
+  (let ((ar (make-array (- end start) :element-type 'integer)))
+    (dotimes (i (- end start) ar)
+      (setf (aref ar i) (+ start i)))))
+
+             
+(defun sieve-of-eratosthenes (max-number)
+  (let ((ar (make-array (+ 1 max-number)
+                        :element-type 'integer))
+        (root-n (ceiling (sqrt max-number))))
+    (dotimes (i (+ 1 max-number))
+      (setf (aref ar i) i))
+    (setf (aref ar 1) 0)
+    (dotimes (i (+ 1 root-n))
+      (when (> (aref ar i) 0)
+        (format t "found prime: ~a~%" i)
+        (do ((j (* i i) (+ j i)))
+            ((> j max-number))
+          (setf (aref ar j) 0))))
+    (remove 0 ar)))
+
+;;    ar))
+;;    (count-if (lambda (x) (> x 0)) ar)))
+
+
+