Two Sieving Problems
August 27, 2013
The count of distinct factors of n is a function known as ω(n) in number theory. Again we use a sieve, but this time the sieve counts each factor instead of clearing a flag:
(define (omega n k)
(let ((sieve (make-vector (+ n 1) 0)) (zs (list)))
(do ((p 2 (+ p 1))) ((< n p))
(when (zero? (vector-ref sieve p))
(do ((i p (+ i p))) ((< n i))
(vector-set! sieve i (+ (vector-ref sieve i) 1)))))
(do ((p 2 (+ p 1))) ((< n p) (reverse zs))
(when (= (vector-ref sieve p) k) (set! zs (cons p zs))))))
The sieve adds 1 for each new factor, and starts at p instead of p2 because it has to find composites as well as primes.
You can see the three programs, with their supporting code, at http://programmingpraxis.codepad.org/gDCKy2xH.