codepad
[
create a new paste
]
login
|
about
Language:
C
C++
D
Haskell
Lua
OCaml
PHP
Perl
Plain Text
Python
Ruby
Scheme
Tcl
; 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))
Private
[
?
]
Run code
Submit