From c04ceb5f29e965bb2d9b37bf38f10f7a12a0cab0 Mon Sep 17 00:00:00 2001
From: bd <bdunahu@operationnull.com>
Date: Sat, 3 Aug 2024 14:48:03 -0600
Subject: Sieve of Eratosthenes implementation and tests

---
 sieve-of-eratosthenes/soe-test.scm | 59 ++++++++++++++++++++++++++++++++++++++
 sieve-of-eratosthenes/soe.scm      | 34 ++++++++++++++++++++++
 2 files changed, 93 insertions(+)
 create mode 100644 sieve-of-eratosthenes/soe-test.scm
 create mode 100644 sieve-of-eratosthenes/soe.scm

diff --git a/sieve-of-eratosthenes/soe-test.scm b/sieve-of-eratosthenes/soe-test.scm
new file mode 100644
index 0000000..69dfaf2
--- /dev/null
+++ b/sieve-of-eratosthenes/soe-test.scm
@@ -0,0 +1,59 @@
+;; -*- compile-command: "guile -L . soe-test.scm"; -*-
+(use-modules (srfi srfi-64)
+             (soe))
+
+
+(test-begin "harness")
+
+
+(test-equal "generate-initial-lst none"
+  '()
+  (generate-initial-lst 0))
+
+(test-equal "generate-initial-lst two"
+  '()
+  (generate-initial-lst 2))
+
+(test-equal "generate-initial-lst four"
+  '(3)
+  (generate-initial-lst 4))
+
+(test-equal "generate-initial-lst five"
+  '(3 5)
+  (generate-initial-lst 5))
+
+(test-equal "generate-initial-lst six"
+  '(3 5)
+  (generate-initial-lst 6))
+
+(test-equal "generate-initial-lst 15"
+  '(3 5 7 9 11 13 15)
+  (generate-initial-lst 15))
+
+(test-equal "generate-primes-to none"
+  '()
+  (generate-primes-to 0))
+
+(test-equal "generate-primes-to two"
+  '(2)
+  (generate-primes-to 2))
+
+(test-equal "generate-primes-to three"
+  '(2 3)
+  (generate-primes-to 3))
+
+(test-equal "generate-primes-to nine"
+  '(2 3 5 7)
+  (generate-primes-to 9))
+
+(test-equal "generate-primes-to thirteen"
+  '(2 3 5 7 11 13)
+  (generate-primes-to 13))
+
+(test-equal "generate-primes-to 977 is 165th"
+  '(977 . 165)
+  (let ((primes (reverse (generate-primes-to 980))))
+    (cons (car primes) (length primes))))
+
+
+(test-end "harness")
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)))
-- 
cgit v1.2.3