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

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

我想到的最简单的是:

>查找数字的所有因素
>获取素数因子[数字本身除外,如果它是素数]并加上它们以检查它是否是一个完美的数字.

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

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

谢谢 !

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

如果输入为奇数,则返回“false”. 🙂

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

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

本站公众号
   欢迎关注本站公众号,获取更多程序园信息
开发小院