From f211fe46db8eba59efbdefad8fe2ec2861921bae Mon Sep 17 00:00:00 2001
From: David Thompson <dthompson2@worcester.edu>
Date: Sun, 2 Feb 2014 15:07:46 -0500
Subject: Solve Problem 3.

---
 problem-3.scm | 38 ++++++++++++++++++++++++++++++++++++++
 1 file changed, 38 insertions(+)
 create mode 100644 problem-3.scm

diff --git a/problem-3.scm b/problem-3.scm
new file mode 100644
index 0000000..9659975
--- /dev/null
+++ b/problem-3.scm
@@ -0,0 +1,38 @@
+(use-modules (srfi srfi-1))
+
+(define (prime-sieve n)
+  (define (mark-multiples! bits x)
+    (define (mark y)
+      (when (< y n)
+        (bitvector-set! bits y #t)
+        (mark (+ y y))))
+    (mark x))
+  (define (sieve m primes bits)
+    (cond ((= m n)
+           primes)
+          ((bitvector-ref bits m)
+           (sieve (1+ m) primes bits))
+          (else
+           (mark-multiples! bits m)
+           (sieve (1+ m) (cons m primes) bits))))
+  (reverse (sieve 2 '() (make-bitvector n))))
+
+(define (divisible? m n)
+  (zero? (modulo m n)))
+
+(define (integer x)
+  (inexact->exact (floor x)))
+
+(define (factors n)
+  (define (factor n primes factors)
+    (cond ((null? primes)
+           factors)
+          ((divisible? n (car primes))
+           (factor (/ n (car primes))
+                   (cdr primes)
+                   (cons (car primes) factors)))
+          (else
+           (factor n (cdr primes) factors))))
+  (factor n (prime-sieve (integer (1+ (sqrt n)))) '()))
+
+(car (factors 600851475143))
-- 
cgit v1.2.3