UVA 10791 - Minimum Sum LCM

Problem link


This is a prime factorization problem with a lot of picky cases.

The first thing to see is that the prim factorization of a number is almost the minimum sum LCM set. I say almost because you have to keep copies of the same factor multipled together.

For example, say N = 36. The prime factorization is 2^2 * 3^2. Obviously the minimum set isn't {2,2,3,3} because this would have an LCM of 6. The set is actually {2^2,3^2} or {4,9}.

So, for *most* cases, just find the prime factorization, keep copies of the same term together, and return the sum of the products (so 4 + 9 = 13 in the above example).

However, there are some issues. First there's N = 1, and N = 2^31 - 1.

For N = 1, you must output 2. This is a little bit counterituitive, because the set {1,1} contains two of the same number, and therefore, isn't truly a set. However, by the problem definition you must have at least two numbers in your set.

For N = 2^31 - 1, you must output 2^31. This is a problem if you're using unsigned integers, of course. But I wouldn't bother changing to signed integers or longs. Just hardcode this case.

The other issue involves numbers that are powers of a single factor. So for instance 5^1, or 2^10. You can't just give {5} or {1024} as your sets, because these have only one number. Instead, you need to add 1 (so {5,1} = 6 and {1024, 1} = 1025).


As far as prime factorization goes, here's how you can do it. We know our limit is 2^31, so we can generate all the primes up to sqrt(2^31) ~= 2^16 using the Sieve of Eratosthenes, and use these to factor N.

Scan through the list of primes from 2 to sqrt(N), and divide N by each prime that it's divisible by (as many times as you can). Keep track of these primes as they are (obviously) factors of N.

Once you've gone through all the primes <= sqrt(N), there will be one of two cases. Either N = 1, in which case you're done, or N > 1, in which case N now equals the last factor of (the original) N. This is because you can have no more than one prime factor greater than the square root of the number. So if N > 1, record N as another factor.

reference


A solution in c++