; 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)
OyB0cmlhbCBkaXZpc2lvbgoKKGRlZmluZSAocHJpbWU/IG4pCiAgKGxldCBsb29wICgoZiAyKSkKICAgIChpZiAoPCBuICgqIGYgZikpCiAgICAgICAgI3QKICAgICAgICAoaWYgKHplcm8/IChtb2R1bG8gbiBmKSkKICAgICAgICAgICAgI2YKICAgICAgICAgICAgKGxvb3AgKCsgZiAxKSkpKSkpCgooZGlzcGxheSAocHJpbWU/IDE2KSkgKG5ld2xpbmUpCihkaXNwbGF5IChwcmltZT8gMTcpKSAobmV3bGluZSkKKGRpc3BsYXkgKHByaW1lPyAxMzI5MDA1OSkpIChuZXdsaW5lKQooZGlzcGxheSAocHJpbWU/IDYwMDg1MTQ3NTE0MykpIChuZXdsaW5lKQoKKGRlZmluZSAoZmFjdG9ycyBuKQogIChsZXQgbG9vcCAoKG4gbikgKGYgMikgKGZzIChsaXN0KSkpCiAgICAoaWYgKDwgbiAoKiBmIGYpKQogICAgICAgIChyZXZlcnNlIChjb25zIG4gZnMpKQogICAgICAgIChpZiAoemVybz8gKG1vZHVsbyBuIGYpKQogICAgICAgICAgICAobG9vcCAoLyBuIGYpIGYgKGNvbnMgZiBmcykpCiAgICAgICAgICAgIChsb29wIG4gKCsgZiAxKSBmcykpKSkpCgooZGlzcGxheSAoZmFjdG9ycyAxNikpIChuZXdsaW5lKQooZGlzcGxheSAoZmFjdG9ycyAxNykpIChuZXdsaW5lKQooZGlzcGxheSAoZmFjdG9ycyAxMzI5MDA1OSkpIChuZXdsaW5lKQooZGlzcGxheSAoZmFjdG9ycyA2MDA4NTE0NTE0MykpIChuZXdsaW5lKQo=