算法检查一个数字是否是一个完美的数字

Question

我正在寻找一种算法来查找给定数字是否是完美数字.

我想到的最简单的是:

1. 找到该数字的所有因素
2. 得到主要因素[除了数字本身,如果它是素数]并将它们加起来检查它是否是一个完美的数字.

有一个更好的方法吗 ？.在搜索时,一些欧几里德的工作出现了,但没有找到任何好的算法.这个golfscript也没有帮助:https://stackoverflow.com/questions/3472534/checking-whether-a-number-is-mathematically-a-perfect-number .

数字等可以在实际使用中缓存等[我不知道在哪里使用完美的数据:)]
但是,由于这是在采访中被问到的,我假设应该有一种"可导出"的方式来优化它.

谢谢 !

Answer 1

如果输入是偶数,请查看它是否为form 2^(p-1)*(2^p-1),with p和2^p-1prime.

如果输入为奇数,则返回"false".:-)

有关详细信息,请参阅Wikipedia页面.

(实际上,由于只有47个完美数字,少于2500万个数字,你可以从一个简单的表开始.问问面试官你是否可以假设你使用的是64位数字,例如......)