Sieve of Eratosthenes implementation and tests

1 files changed, 34 insertions, 0 deletions

diff --git a/sieve-of-eratosthenes/soe.scm b/sieve-of-eratosthenes/soe.scm
new file mode 100644
index 0000000..4b83a97
--- /dev/null
+++ b/sieve-of-eratosthenes/soe.scm
@@ -0,0 +1,34 @@
+(define-module (soe)
+  #:export (generate-primes-to
+            generate-initial-lst))
+
+
+(define (generate-primes-to n)
+
+  (define (sieve buffer accept prev-size)
+    (if (or (null? buffer)
+            ;; if filter removes nothing, we are done.
+            ;; sub one because we always move an element into accepted
+            (eq? (length buffer) (1- prev-size)))
+        (append (reverse accept) buffer)
+        (let ((curr (car buffer))
+              (size (length buffer)))
+          (sieve
+           (filter
+            (lambda (x) (not (eq? (remainder x curr) 0)))
+            buffer)
+           (cons curr accept)
+           size))))
+
+  (let ((buffer (generate-initial-lst n))
+        (accept '(2)))
+    (if (> 2 n)
+        '()
+        (sieve buffer accept -1))))
+
+(define (generate-initial-lst n)
+  "Generates a list of odd numbers
+up to N."
+  (if (> 3 n)
+      '()
+      (iota (floor (/ (1- n) 2)) 3 2)))