; factor tables
(define (lpf-sieve n)
(let* ((len (quotient (- n 1) 2))
(lpf (make-vector len 1)))
(let loop ((i 0) (p 3))
(cond ((< n (* p p)) lpf)
((= (vector-ref lpf i) 1)
(do ((j (+ (* 2 i i) (* 6 i) 3) (+ j p)))
((<= len j) (loop (+ i 1) (+ p 2)))
(when (= (vector-ref lpf j) 1)
(vector-set! lpf j p))))
(else (loop (+ i 1) (+ p 2)))))))
(define lpf (lpf-sieve 1000000))
(define (factors n)
(let loop ((n n) (fs (list)))
(if (= n 1) (reverse fs)
(let ((f (if (even? n) 2 (vector-ref lpf (/ (- n 3) 2)))))
(if (= f 1) (reverse (cons n fs)) (loop (/ n f) (cons f fs)))))))
(define (show-table k n00)
(define (p->i p) (/ (- p 3) 2))
(display " ")
(do ((j 0 (+ j 1))) ((= j k) (newline))
(show5 (+ j n00)))
(do ((i 0 (+ i 10))) ((= i 100))
(do ((ns '(1 3 7 9) (cdr ns))) ((null? ns))
(show2 (+ i (car ns)))
(do ((j 0 (+ j 1))) ((= j k))
(let ((p (+ (* 100 (+ j n00)) (+ i (car ns)))))
(if (= p 1) (display " ")
(let ((f (vector-ref lpf (p->i p))))
(if (= f 1) (display " --") (show5 f))))))
(newline))))
(define (show2 num)
(if (< num 10) (display " "))
(display num))
(define (show5 num)
(if (< num 10) (display " ")
(if (< num 100) (display " ")
(if (< num 1000) (display " ")
(if (< num 10000) (display " ")))))
(display num))
(show-table 10 0) (newline)
(show-table 10 9990) (newline)
(define (totients n)
(let ((tots (make-vector (+ n 1))))
(do ((i 0 (+ i 1))) ((< n i))
(vector-set! tots i i))
(do ((i 2 (+ i 1))) ((< n i) tots)
(when (= i (vector-ref tots i))
(vector-set! tots i (- i 1))
(do ((j (+ i i) (+ i j))) ((< n j))
(vector-set! tots j
(* (vector-ref tots j) (- 1 (/ i)))))))))
(display (totients 100))