分类:
2010-03-27 16:24:09
好像是一次笔试题,以下是我当时的回答,也不知道考官是怎么看的,应该有更好的解决办法。
题目:给定自然数N,若N为1或者素数,则和为N。否则分解N为若干自然数的和,求最小的和。
思想:首先要解决怎样分解和才最小,对于任何大于2的自然数a, b, 则1/a + 1/b < 1/2 + 1/2 = 1. 所以a + b < ab。所以对于N的任何一个因子m, 若m=ab,由于m>a+b,所以应该将m分解成a和b。所以和最小的情况是将N分解成所有的素数乘积。
|