Divisor Counts ⧉

Pretty straight-forward problem. I struggled to allocate the memory at first (embarrassing), only to be reminded that I need to either globally allocate my non-const array or tag it with static. Silly mistakes. The solution is basically the Sieve of Eratosthenes except instead of a tagging numbers as composisite you increment a count of their divisors.

divisor_counts.cpp

divisor_counts.py

#include <array>
#include <iostream>
constexpr int kMaxSize = 3000001;
int main() {
  int n;
  std::cin >> n;
  std::ios_base::sync_with_stdio(false);
  std::cin.tie(NULL);
  static std::array<int, kMaxSize> divcount {};
  std::fill(divcount.begin()+2, divcount.end(), 2);
  std::cout << 1 << '\n';
  for (int i = 2; i <= n; ++i) {
    for (int j = 2; j <= n; ++j) {
        if (i*j > n) break;
        divcount[i*j]++;
    }
    std::cout << divcount[i] << '\n';
  }
  return 0;
}

If you found this solution helpful, consider leaving a star!