[ create a new paste ] login | about

Link: http://codepad.org/pvCamAkP    [ raw code | output | fork ]

programmingpraxis - Scheme, pasted on Jul 14:
; how many distinct products in a times table?

(define (m n) ; brute force
  (let ((bits (make-vector (+ (* n n) 1) #f)))
    (do ((i 1 (+ i 1))) ((< n i))
      (do ((j i (+ j 1))) ((< n j))
        (vector-set! bits (* i j) #t)))
    (do ((k 1 (+ k 1))
         (c 0 (+ c (if (vector-ref bits k) 1 0))))
          ((< (* n n) k) c))))

(display (m 1000)) (newline)

(define (m n) ; sieve
  (let ((bits (make-vector (+ (* n n) 1) #f)))
    (do ((i 1 (+ i 1))) ((< n i))
      (do ((j (* i i) (+ i j))) ((< (* i n) j))
        (vector-set! bits j #t)))
    (do ((k 1 (+ k 1))
         (c 0 (+ c (if (vector-ref bits k) 1 0))))
        ((< (* n n) k) c))))

(display (m 1000)) (newline)


Output:
1
2
248083
248083


Create a new paste based on this one


Comments: