diff options
| -rw-r--r-- | problem-3.scm | 42 |
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) |