enum-integers-with-the-factors-optimized.cpp

#include <iostream>
#include <vector>
#include <cmath>

using namespace std;

const int N = 1e5;

vector<int> primes;

void init(void)
{
  vector<bool> v(N+1, true);
  for (int i = 2, root = sqrt(N); i <= root; i++) {
    if (v[i] == false) continue;
    for (int j = i*i; j <= N; j += i) v[j] = false;
  }
  for (int i = 2; i <= N; i++) {
    if (v[i] == true) primes.push_back(i);
  }
}

void enumerate(void)
{
  vector<int> factors;
  for (uint64_t n = 1, i = 0; true; ) {

    if (n <= N) {
      cout << n << " = ";
      for (size_t j = 0; j+1 < factors.size(); j++) {
        cout << primes[factors[j]] << " * ";
      }
      cout << (factors.empty() ? 1 : primes[factors.back()]) << endl;

      n *= primes[i];
      factors.push_back(i);
    } else {
      const auto lowest = factors.back(); factors.pop_back();
      const auto booby = factors.back(); factors.pop_back();
      if (primes.size() <= booby+1) return;
      n = n / (static_cast<uint64_t>(primes[lowest]) * primes[booby]) * primes[booby+1];
      factors.push_back(booby+1);
      i = booby+1;
    }

  }
}

int main(void)
{
  init();
  enumerate();
}