一尘不染

检查数字是否为完美数字的算法

algorithm

我正在寻找一种算法,以查找给定的数字是否为理想数字。

我想到的最简单的是:

  1. 找出所有影响人数的因素
  2. 获得质数因子(数字本身除外,如果是质数则除外),并将它们加起来以检查它是否为理想数。

有一个更好的方法吗
?。在搜索时,出现了一些Euclids工作,但是没有找到任何好的算法。另外,这个golfscript也无济于事 。

数字等可以在现实世界中使用时进行缓存[我不知道在哪里使用完美的否定::]]
但是,由于这是在采访中提出的,因此我认为应该有一种“可派生的”方式来优化它。

谢谢 !


阅读 254

收藏
2020-07-28

共1个答案

一尘不染

如果输入为偶数,则查看其输入形式是否为2^(p-1)*(2^p-1)with p2^p-1prime。

如果输入为奇数,则返回“ false”。:-)

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

(实际上,由于只有47个完美数字且少于2500万个数字,因此您可以从一个简单的表格开始。例如,询问访问员是否可以假设您使用的是64位数字…)

2020-07-28