检查数字是否为完美数字的算法 [英] Algorithm to check if a number if a perfect number

问题描述

我正在寻找一种算法来确定给定的数字是否为理想数字.

I am looking for an algorithm to find if a given number is a perfect number.

我想到的最简单的是:

1. 找出数字的所有因素
2. 获取质数因子(数字本身除外，如果是质数的话)，然后将它们加起来以检查它是否为完美数.

是否有更好的方法可以做到这一点? 在搜索时，出现了一些Euclids工作，但是没有找到任何好的算法.另外，这个golfscript也无济于事: https://stackoverflow.com/Questions/3472534/检查数字是否在数学上是一个完美的数字.

Is there a better way to do this ?. On searching, some Euclids work came up, but didnt find any good algorithm. Also this golfscript wasnt helpful: https://stackoverflow.com/questions/3472534/checking-whether-a-number-is-mathematically-a-perfect-number .

数字等可以在实际使用中进行缓存[我不知道在哪里使用完美的数字:)]
但是，由于这是在采访中提出的，因此我认为应该有一种可派生的"方式来优化它.

The numbers etc can be cached etc in real world usage [which I dont know where perfect nos are used :)]
However, since this is being asked in interviews, I am assuming there should be a "derivable" way of optimizing it.

谢谢！

推荐答案

如果输入是偶数，请查看它是否为2^(p-1)*(2^p-1)形式，且带有p和2^p-1质数.

If the input is even, see if it is of the form 2^(p-1)*(2^p-1), with p and 2^p-1 prime.

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

If the input is odd, return "false". :-)

有关详细信息，请参见维基百科页面.

See the Wikipedia page for details.

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

(Actually, since there are only 47 perfect numbers with fewer than 25 million digits, you might start with a simple table of those. Ask the interviewer if you can assume you are using 64-bit numbers, for instance...)

这篇关于检查数字是否为完美数字的算法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！