小学数学题，你会吗？

sqfasd

我错了~~~~~

sqfasd

回复 3# pmerofc

刚提交完答案就发现我错了

我只证明了分解到最小的素数，但分解为3还是2我没考虑，现在看来结果应改为优先把3分解出去，还不知道怎么证明

N除以3余几
1.正好除尽，结果为3^(N/3)
2.余2，结果为3^(N/3)*2
3.余1，结果为3^(N/3-1)*2*2

sqfasd

根据3^2> 2^3
有
3^(2x) > 2^(3x)
令N=6X
3^(N/3) > 2^(N/2)

还不是很严谨，有些细节要补充，但大概说明了为什么分解为3要比分解为2，积更大

sqfasd

回复 6# pmerofc

首先，分解的素数里，不能有3和2以外的数，如果有3和2以外的数，那么继续分解，肯定积更大
然后就是证明是主要分解为3还是主要分解为2，5楼已经证明了

daybreakcx

动态规划应该行的吧

1. #include <stdio.h>
   
2. 
   
3. #define MAX(x,y) ((x)>(y)?(x):(y))
   
4. 
   
5. int bst[17], prime[7] = {6, 2, 3, 5, 7, 11, 13}, i, j;
   
6. 
   
7. int main()
   
8. {
   
9.         for (bst[0] = 1, i = 1; i <= 16; ++i)
   
10.                 for (bst[i] = -1, j = 1; j <= 6 && i >= prime[j]; ++j)
    
11.                         bst[i] = MAX(bst[i], bst[i - prime[j]] * prime[j]);
    
12.         printf("%d\n", bst[16]);
    
13.         return 0;
    
14. }
    

复制代码