## 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 *p*^{2} 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.

My first answers are in J; it’s definitely cheating when your language has a

“prime factors of” function.

Problem 1:

This takes a very long time to get anywhere; the second is much faster:

I originally had simpler answers, but decided that only working over odd

numbers (first question) or numbers equivalent to 1 mod 4 (second question) was

worth the uglification of my code.

My second answers are in Ruby; I can’t imagine trying to do these in a language

like C or C++, even with the help of multiprecision libraries like GMP or NTL.

I went with the Miller-Rabin primality test.

A Python version with segments.