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.

Posted by programmingpraxis

Filed in Exercises

4 Comments »

4 Responses to “Highly Composite Numbers, A Sieving Approach”

Daniel said

July 23, 2016 at 12:56 PM

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:

[1, 2, 4, 6, 12, 24, 36, 48, 60, 120, 180, 240, 360, 720, 840, 1260, 1680, 2520, 5040, 7560, 10080, 15120, 20160, 25200, 27720, 45360, 50400, 55440, 83160, 110880, 166320, 221760, 277200, 332640, 498960, 554400, 665280, 720720, 1081080, 1441440, 2162160]

Daniel said

July 23, 2016 at 1:04 PM

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);
}

Daniel said
July 23, 2016 at 1:05 PM
> “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”.
Highly Abundant Numbers | Programming Praxis said
December 20, 2016 at 9:01 AM
[…] 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 […]

Programming Praxis