; trial division

(define (prime? n)
  (let loop ((f 2))
    (if (< n (* f f))
        #t
        (if (zero? (modulo n f))
            #f
            (loop (+ f 1))))))

(display (prime? 16)) (newline)
(display (prime? 17)) (newline)
(display (prime? 13290059)) (newline)
(display (prime? 600851475143)) (newline)

(define (factors n)
  (let loop ((n n) (f 2) (fs (list)))
    (if (< n (* f f))
        (reverse (cons n fs))
        (if (zero? (modulo n f))
            (loop (/ n f) f (cons f fs))
            (loop n (+ f 1) fs)))))

(display (factors 16)) (newline)
(display (factors 17)) (newline)
(display (factors 13290059)) (newline)
(display (factors 60085145143)) (newline)