Highly Composite Numbers, A Sieving Approach
July 19, 2016
We’ve seen programs to compute the sequence of highly composite numbers in two previous exercises. Today, we look at a third algorithm, based on the Sieve of Eratosthenes.
If you have to find a the divisors of a number, or count them, you can employ the brute-force method of testing each possible divisor from 1 to n, as in the first solution to this problem, or you can factor n and compute the divisors, as we have done in a previous exercise. But if you have to find the divisors of a bunch of numbers, in sequence, you can sieve for them; we also did that in a previous exercise. Once you know the divisor-count for each number from 1 to n, a simple sequential scan looking for successive records will create the list of highly composite numbers.
Your task is to write a program to calculate highly composite numbers less than a limit n using a sieving algorithm. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.
Programming Praxis 