求 5000 以内的所有“水仙花数” 解法

[flyinflash]

求 5000 以内的所有“水仙花数”。

备注：在数论中，水仙花数是指这样一个数，其各个数之立方和等于该数。如，1^3+5^3+3^3=153。
* 十进制中的这样的数有：0、1、2、3、4、5、6、7、8、9、153、370、371,
* 三进制中的这样的数有：0、1、2、12、122
* 四进制中的这样的数有：0、1、2、3、313

http://en.wikipedia.org/wiki/Narcissistic_number
http://zh.wikipedia.org/wiki/水仙花数

代码： 全选

int i, tmp, k, sum;
for ( k = 3; k <= MAX_VAL ; k ++ )
{
	for ( i = k, tmp = i % 10, sum = 0; i != 0 && i > 0; i /= 10, tmp = i % 10 )
		sum += tmp * tmp * tmp;
	if (sum == k)
		printf("%d \n", sum);
}

更优解是？

[@小天@]

感觉是可以优化的。
首先，上界是可以优化，类似于5000以内，那么在这之内的各个位上立方和最大为4^3+9^3+9^3+9^3＝2251(4999)，显然比5000小，所以上界可以改进。
类似的，如果是6987这类的限制，就去5999的立方和比较，取其中最大的作为上界。可以看出上界约束虽然对1000以内的约束不强，可是对5000以上有很好的改进。因为就算是1亿以内的数字，最大不过是8*9^3=5832。
还有，我觉得在循环求和那里是不是也可以优化一下，因为，类似于993这类的数字，在得到前两个9的立方和后就可以排除了，在for循环里加个判断条件早点continue掉。