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.
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.