求教一个完美数的算法?能算至少20个,必有重谢!

Question

如题所述

Answer 1

大数学家欧拉曾推算出完全数的获得公式：如果p是质数,且2^p-1也是质数,那么（2^p-1）*2^（p-1）便是一个完全数.
　　当2^p-1是质数的时候,称其为梅森素数.至今,人类只发现了47个梅森素数,也就是只发现了47个完全数.
　　第20个对应p=4423,有1332位长.
大概的算法是这样：（a^k表示a的k次方,不是C/C++中的异或）
1.用筛法求10000以内素数；
2.对每个素数p,用miller-robin算法判定(2^p-1)是否为素数；
2.1 若2^p-1为素数,计算出(2^p-1)*(2^(p-1))即为完全数.
这个范围的完全数共有26个,需要实现高精度运算.