整数分解

题目描述

整数分解(版本2) 一个正整数可以分解成若干个自然数之和。请你编一个程序，对于给出的一个正整数n(1< =n< =1500)，求出满足要求的分解方案，并使这些自然数的乘积m达到最大。 例如n=10，则可以分解为2+2+3+3，乘积m=2*2*3*3=36

输入

一个正整数n

输出

输出分解的自然数的最大乘积m

样例

提示

通过对这道题的分析，可以发现：
如果n==1,2,3,则不用分；
如果n=4，则分成两个2和部分都是一样的；
如果n==5，则分成2和3是最大的；
如果n==6，则分成3和3是最大的；
如果n==7，则分成4和3是最大的；
如果n==8，则分成2和3和3是最大的；
如果n==9，则分成3和3和3是最大的；
……
总结规律，我们可以发现如果一个数大于4的情况下，我们只要不断地分3就可以了。而这就是我们的解法。

来源/分类