; 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)