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

Pages: 1 2

Here’s a solution in C++.

Output:

The inner loop should go up to n, not n+1. I originally wrote the function to print all highly composites including n, but then saw the instructions say less than n. When updating, I mistakenly didn’t correct that inner loop bound. The code still seemingly worked with the out-of-bounds bug. Here’s the corrected version.

> “The inner loop should go up to n, not n+1”

I meant to say “The inner loop should go up to n-1, not n”.