What is the smallest positive number that is evenly divisible by all of the numbers from 1 to 20? http://projecteuler.net/problem=5

number-divisible-by-numbers.cc

// Question: What is the smallest number divisible by each of the
//           numbers 1 to 20?
//
// I factorize each of the numbers 1 to 20.  For example, 12=2*2*3.
// This factorization can be represented by a histogram (2*2 3*1).  If
// a number is evenly divisible by 20, it must be a product of at
// least two 2's and a 3.  So I accumulate each factorization into a
// histogram by the following rule: if the factorization contains two
// 2's, the accumulation must contain at least two 2's.  Then the
// final result is the product of numbers in the accumulation.

#include <math.h>
#include <stdio.h>
#include <map>

typedef std::map<int, int> Map;
typedef Map::const_iterator MapIter;

int find_smallest_divisor(int number) {
  for (int i = 2; i <= sqrt(number); ++i) {
    if (number % i == 0) {
      return i;
    }
  }
  return number;
}

void factorize(int number, Map* prime_factors) {
  prime_factors->clear();
  for (int divisor = find_smallest_divisor(number);
       divisor != number;
       divisor = find_smallest_divisor(number)) {
    (*prime_factors)[divisor]++;
    printf("%d ", divisor);
    number = number / divisor;
  }
  (*prime_factors)[number]++;
  printf("%d\n", number);
}

void accumulate_factors(Map* accum, const Map& factors) {
  for (MapIter i = factors.begin(); i != factors.end(); ++i) {
    if ((*accum)[i->first] < i->second) {
      (*accum)[i->first] = i->second;
    }
  }
}

int main() {
  Map prime_factors;
  Map accum;
  for (int i = 1; i <= 20; ++i) {
    printf("Factors of %d: ", i);
    factorize(i, &prime_factors);
    accumulate_factors(&accum, prime_factors);
  }

  printf("Product of factors: ");
  int product = 1;
  for (MapIter i = accum.begin(); i != accum.end(); ++i) {
    printf("%d^%d ", i->first, i->second);
    product *= (int)powf(i->first, i->second);
  }
  printf("%d\n", product);

  return 0;
}