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 
Here’s a solution in C++.
#include <cstdio> #include <vector> using std::vector; // Computes the highly composite numbers less than n. void HighlyComposites(const int n, vector<int>* highly_composites) { vector<int> divisor_counts(n, 0); for (int i = 1; i < n; ++i) { for (int j = i; j <= n; j += i) { divisor_counts[j]++; } } int max_divisors = 0; for (int i = 1; i < n; ++i) { int divisor_count = divisor_counts[i]; if (divisor_count > max_divisors) { highly_composites->push_back(i); max_divisors = divisor_count; } } } void PrintVector(const vector<int>& v) { printf("["); for (int i = 0; i < v.size(); ++i) { if (i > 0) printf(", "); printf("%d", v[i]); } printf("]\n"); } int main(int argc, char* argv[]) { vector<int> highly_composites; int limit = 2162160 + 1; // t make sure you get them all up to 2,162,160 HighlyComposites(limit, &highly_composites); PrintVector(highly_composites); }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.
#include <cstdio> #include <vector> using std::vector; // Computes the highly composite numbers less than n. void HighlyComposites(const int n, vector<int>* highly_composites) { vector<int> divisor_counts(n, 0); for (int i = 1; i < n; ++i) { for (int j = i; j < n; j += i) { divisor_counts[j]++; } } int max_divisors = 0; for (int i = 1; i < n; ++i) { int divisor_count = divisor_counts[i]; if (divisor_count > max_divisors) { highly_composites->push_back(i); max_divisors = divisor_count; } } } void PrintVector(const vector<int>& v) { printf("["); for (int i = 0; i < v.size(); ++i) { if (i > 0) printf(", "); printf("%d", v[i]); } printf("]\n"); } int main(int argc, char* argv[]) { vector<int> highly_composites; int limit = 2162160 + 1; // t make sure you get them all up to 2,162,160 HighlyComposites(limit, &highly_composites); PrintVector(highly_composites); }> “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”.
[…] studied highly composite numbers in a series of several previous exercises, and had a lot of fun. In today’s exercise we look at a related concept: highly […]