diff options
| -rw-r--r-- | problem-3.scm | 38 |
1 files changed, 38 insertions, 0 deletions
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)) |