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

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

  1. Daniel said

    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]
    
  2. Daniel said

    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);
    }
    
  3. Daniel said

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

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: