[ create a new paste ] login | about

Project: programmingpraxis
Link: http://programmingpraxis.codepad.org/a9eDAmhr    [ raw code | output | fork ]

programmingpraxis - Scheme, pasted on May 6:
; 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))


Output:
  0 1 2 3 4 5 6 7 8 9
 1  -- 3 7 -- 3 -- -- 3 17
 3 -- -- 7 3 13 -- 3 19 11 3
 7 -- -- 3 -- 11 3 -- 7 3 --
 9 3 -- 11 3 -- -- 3 -- -- 3
11 -- 3 -- -- 3 7 13 3 -- --
13 -- -- 3 -- 7 3 -- 23 3 11
17 -- 3 7 -- 3 11 -- 3 19 7
19 -- 7 3 11 -- 3 -- -- 3 --
21 3 11 13 3 -- -- 3 7 -- 3
23 -- 3 -- 17 3 -- 7 3 -- 13
27 3 -- -- 3 7 17 3 -- -- 3
29 -- 3 -- 7 3 23 17 3 -- --
31 -- -- 3 -- -- 3 -- 17 3 7
33 3 7 -- 3 -- 13 3 -- 7 3
37 -- -- 3 -- 19 3 7 11 3 --
39 3 -- -- 3 -- 7 3 -- -- 3
41 -- 3 -- 11 3 -- -- 3 29 --
43 -- 11 3 7 -- 3 -- -- 3 23
47 -- 3 13 -- 3 -- -- 3 7 --
49 7 -- 3 -- -- 3 11 7 3 13
51 3 -- -- 3 11 19 3 -- 23 3
53 -- 3 11 -- 3 7 -- 3 -- --
57 3 -- -- 3 -- -- 3 -- -- 3
59 -- 3 7 -- 3 13 -- 3 -- 7
61 -- 7 3 19 -- 3 -- -- 3 31
63 3 -- -- 3 -- -- 3 7 -- 3
67 -- -- 3 -- -- 3 23 13 3 --
69 3 13 -- 3 7 -- 3 -- 11 3
71 -- 3 -- 7 3 -- 11 3 13 --
73 -- -- 3 -- 11 3 -- -- 3 7
77 7 3 -- 13 3 -- -- 3 -- --
79 -- -- 3 -- -- 3 7 19 3 11
81 3 -- -- 3 13 7 3 11 -- 3
83 -- 3 -- -- 3 11 -- 3 -- --
87 3 11 7 3 -- -- 3 -- -- 3
89 -- 3 17 -- 3 19 13 3 7 23
91 7 -- 3 17 -- 3 -- 7 3 --
93 3 -- -- 3 17 -- 3 13 19 3
97 -- -- 3 -- 7 3 17 -- 3 --
99 3 -- 13 3 -- -- 3 17 29 3

  9990 9991 9992 9993 9994 9995 9996 9997 9998 9999
 1 19 -- 3 181 13 3 29 107 3 7
 3 3 7 89 3 83 191 3 37 7 3
 7 -- 17 3 -- 37 3 7 43 3 --
 9 3 127 17 3 31 7 3 223 -- 3
11 13 3 41 17 3 23 -- 3 487 11
13 347 79 3 7 17 3 -- 11 3 19
17 859 3 -- 11 3 281 17 3 7 --
19 7 11 3 641 19 3 157 7 3 991
21 3 191 -- 3 53 -- 3 -- 17 3
23 -- 3 31 13 3 7 -- 3 11 17
27 3 229 541 3 11 53 3 -- 139 3
29 -- 3 7 -- 3 -- 37 3 167 7
31 11 7 3 -- -- 3 -- 599 3 --
33 3 -- -- 3 -- 19 3 7 23 3
37 13 29 3 233 -- 3 59 47 3 113
39 3 277 -- 3 7 41 3 13 283 3
41 71 3 61 7 3 -- 149 3 67 577
43 -- 23 3 19 73 3 47 653 3 7
47 7 3 383 31 3 193 11 3 467 13
49 -- -- 3 13 11 3 7 -- 3 29
51 3 73 11 3 -- 7 3 71 37 3
53 11 3 29 163 3 -- -- 3 -- --
57 3 821 7 3 19 13 3 11 109 3
59 107 3 37 -- 3 11 29 3 7 --
61 7 31 3 11 503 3 13 7 3 --
63 3 11 223 3 601 -- 3 -- -- 3
67 -- 13 3 911 7 3 -- 173 3 31
69 3 -- -- 3 151 83 3 -- 13 3
71 83 3 7 -- 3 19 -- 3 127 7
73 17 7 3 23 257 3 479 -- 3 13
77 19 3 17 -- 3 199 7 3 691 11
79 29 199 3 17 13 3 163 11 3 --
81 3 -- 23 3 7 11 3 31 73 3
83 -- 3 59 7 3 13 -- 3 -- --
87 3 7 -- 3 107 79 3 17 7 3
89 7 3 331 -- 3 73 137 3 11 19
91 -- 19 3 97 -- 3 7 13 3 17
93 3 13 41 3 11 7 3 43 71 3
97 11 97 3 7 499 3 953 433 3 757
99 3 -- 7 3 -- -- 3 19 307 3

#(0 1 1 2 2 4 2 6 4 6 4 10 4 12 6 8 8 16 6 18 8 12 10 22 8 20 12 18 12 28 8 30 16 20 16 24 12 36 18 24 16 40 12 42 20 24 22 46 16 42 20 32 24 52 18 40 24 36 28 58 16 60 30 36 32 48 20 66 32 44 24 70 24 72 36 40 36 60 24 78 32 54 40 82 24 64 42 56 40 88 24 72 44 60 46 72 32 96 42 60 40)


Create a new paste based on this one


Comments: