(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))