For n
For n > = 4, it can be proved that it can be decomposed into the sum of several numbers so that the product is not less than n.
If it is decomposed into 1 and n- 1, it does not help the product, so we assume n.
Decomposition into a and n-a, 2
a * (n - a) - n
= (a - 1) * n - a * a + a - a
= (a - 1) * (n - a) - a
& gt= (a - 1) * 2 - a
= a - 2
& gt= 0
If a, n-a is still >; = 4, and then continue to decompose until a, n-a.
Increase, so the optimal solution must be the final decomposition result, that is, all the decomposed numbers are 2 or 3.
( 1)
Suppose n is an even number, which is decomposed into a 2 and b 3, that is, n = 2 * a+3 * b, then the product is 2a * 3b.
Please note that 23
The optimal scheme is decomposed into n/6 * 2 3s and n% 6/2 2s, and the product is 3n/6*2 * 2n%6/2.
(2)
Suppose n is an odd number and a 3 must be separated, then n-3 is an even number. So the best solution is decomposition.
(n-3)/6*2+ 1 3s and (n-3)%6/2 2s, the product is 3(n-3)/6*2+ 1 * 2(n-3)%6/2.