summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
-rw-r--r--problem-3.scm38
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))