I am writing a program that processes data based on an integer factor. The process can either be done at once, or in multiple stages. For example, one stage with factor 500 could be replaced by three stages, the first one with factor 50, the second with factor 5, the third with factor 2. Because, 50*5*2 = 500. The reason for this is that the run-time complexity of the code is directly proportional to this integer.
It is best to order these sub-factors by size, largest first. Like in the example above: [50,5,2]. But, it is also best to make sure that the sum of these sub-factors is as small as possible. This means for example that [10,10,5] is better than [50,5,2], because the sum of the former is 25, while the sum of the latter is 57. This sum defines the run-time complexity, as mentioned above. The lower the number, the less work needs to be done, and the faster the code is.
It is of course possible that a factor simply cannot be decomposed into exactly the given number of sub-factors. One example is 25: Here, only [5,5] is possible. For this reason, I want something that decomposes an integer number into up to N numbers (N being a user specified parameter), with the constraint above about the sum of these numbers being as small as possible.
So far, I've had no luck finding anything that solves this. Does anybody know more?