Improve solution to problem 3.

1 files changed, 9 insertions, 33 deletions

diff --git a/problem-3.scm b/problem-3.scm
index 9659975..81e899e 100644
--- a/problem-3.scm
+++ b/problem-3.scm
@@ -1,38 +1,14 @@
-(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)))
+(define (largest-prime-factor n)
+  (define (inner n d)
+    (cond ((= d n)
+           d)
+          ((divisible? n d)
+           (inner (/ n d) d))
           (else
-           (factor n (cdr primes) factors))))
-  (factor n (prime-sieve (integer (1+ (sqrt n)))) '()))
+           (inner n (1+ d)))))
+  (inner n 2))
 
-(car (factors 600851475143))
+(largest-prime-factor 600851475143)