问题1150--求完全数

1150: 求完全数

[命题人 : ]
时间限制 : 1.000 sec  内存限制 : 128 MB

题目描述

完全数(Perfect number),又称完美数或完备数,是一些特殊的自然数。它所有的真因子(即除了自身以外的约数)的和(即因子函数),恰好等于它本身。
如果一个数恰好等于它的真因子之和,则称该数为“完全数”。完全数:因子之和等于它本身的自然数,如6=1+2+3

求正整数2和n之间的完全数(一行一个数)。

输入

输入n(n≤5000)。

输出

一行一个数,按由小到大的顺序。

样例输入 Copy

7

样例输出 Copy

6

提示

完全数(Perfect number),又称完美数或完备数,是一些特殊的自然数。它所有的真因子(即除了自身以外的约数)的和(即因子函数),恰好等于它本身。
性质:
所有的完全数都是三角形数。例如:6=1+2+3;28=1+2+3+...+6+7;496=1+2+3+...+30+31;8128=1+2+3…+126+127。

计算方法
1.推导公式
大数学家欧拉曾推算出完全数的获得公式:如果p是质数,且2p-1也是质数,那么(2p-1)X2(p-1)便是一个完全数。
例如p=2,是一个质数,2p-1=3也是质数,(2p-1)X2(p-1)=3X2=6,是完全数。
例如p=3,是一个质数,2p-1=7也是质数,(2p-1)X2(p-1)=7X4=28,是完全数。
例如p=5,是一个质数,2p-1=31也是质数,(2p-1)X2(p-1)=31X16=496是完全数。
但是2p-1什么条件下才是质数呢?事实上,当2p-1是质数的时候,称其为梅森素数。到2013年2月6日为止,人类只发现了48个梅森素数,较小的有3、7、31、127等。
2.计算机枚举法
就是接下来你要使用的方法^_^。