blob: 9659975548d379f6a92246907d6c96e8f7809816 (
plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
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))
|
