读书人

欧拉计划:扭结的第23题找出所有不能

发布时间: 2012-12-22 12:05:05 作者: rapoo

欧拉计划:纠结的第23题,找出所有不能表示为两个过剩数之和的正整数之和,优化后7s可以执行完,再优化5秒

如果一个数的所有真因子之和等于这个数,那么这个数被称为完全数。例如,28的所有真因子之和为1 + 2 + 4 + 7 + 14 = 28,所以28是一个完全数。

如果一个数的所有真因子之和小于这个数,称其为不足数,如果大于这个数,称其为过剩数。

12是最小的过剩数,1 + 2 + 3 + 4 + 6 = 16。因此最小的能够写成两个过剩数之和的数字是24。经过分析,可以证明所有大于28123的数字都可以被写成两个过剩数之和。但是这个上界并不能被进一步缩小,即使我们知道最大的不能表示为两个过剩数之和的数字要比这个上界小。

找出所有不能表示为两个过剩数之和的正整数之和。


纠结并不是因为这道题目有多么难,程序很快就写出来了,

分为两部,首先求出小于28123的过剩数。并把他们放在数组和哈希中,放在数组中是为了遍历,放在hash中是为了查找方便

其次,遍历1到28123,遍历数组,如果当前数减去数组里的一个数载哈希中存在,那么久pass。

这个程序的效率不高。有1分钟以上。

程序如下:

C:\WINDOWS\system32\cmd.exe /c perl "C:\Documents and Settings\A面\names.pl"41798715Hit any key to close this window...



读书人网 >编程

热点推荐