8

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

我想到的最简单的是：

  1. 找出数字的所有因数
  2. 获取素数[除了数字本身，如果它是素数]并将它们相加以检查它是否是一个完美的数字。

有一个更好的方法吗 ？。在搜索中，出现了一些 Euclids 工作，但没有找到任何好的算法。这个 Golfscript 也没有帮助：https ://stackoverflow.com/questions/3472534/checking-whether-a-number-is-mathematically-a-perfect-number 。

数字等可以在现实世界的使用中被缓存等[我不知道在哪里使用完美的数字:)]
但是，由于这是在采访中被问到的，我假设应该有一种“可推导”的优化方式。

谢谢 ！

4

4 回答 4

11

如果输入是偶数，看看它是否是2^(p-1)*(2^p-1), withp和2^p-1prime 形式。

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

有关详细信息，请参阅维基百科页面。

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

于 2011-07-04T03:50:26.817 回答
0

编辑：该死，我面试失败了！:-(
在我过分热心地尝试寻找技巧或启发式方法来改进“因式分解 + 枚举除数 + 求和”方法时，我没有注意到 1 模 9 仅仅是必要的，而且肯定不是at数字（除了 6 之外）是完美的......
Duh......平均有九分之一的偶数满足这个条件，我的算法肯定会找到太多完美的数字;-)。
为了救赎自己，坚持并维持使用数字根的建议，但仅作为过滤器，以避免在大多数情况下对因子进行更昂贵的计算。

【原创尝试：耻辱殿】

If the number is even,<br>
   compute its [digital root][1].
       if the digital root is 1, the number is perfect, otherwise it isn't.

If the number is odd...
   there are no shortcuts, other than...
       "Not perfect" if the number is smaller than 10^300
       For bigger values, one would then need to run the algorithm described in 
       the question, possibly with a few twists typically driven by heuristics
       that prove that the sum of divisors will be lacking when the number
       doesn't have some of the low prime factors.

我建议偶数的数字根技巧的原因是，这可以在没有任意长度算术库（如 GMP）的帮助下计算。它的计算成本也比素因子分解和/或因式分解 (2^(p-1) * ((2^p)-1)) 低得多。因此，如果面试官对奇数的“没有完美”的回答感到满意，那么该解决方案在大多数计算机语言中都是非常有效且可编码的。

【第二次和第三次尝试……】

If the number is even,<br>
   if it is 6
      The number is PERFECT
   otherwise compute its [digital root][1].
       if the digital root is _not_ 1
           The number is NOT PERFECT
       else ..., 
           Compute the prime factors
           Enumerate the divisors, sum them
           if the sum of these divisor equals the 2 * the number
                it is PERFECT
           else
                it is NOT PERFECT

If the number is odd...
    same as previously

关于这个相对奇怪的面试问题......
我赞同 andrewdski对这篇文章中另一个回复的评论，即这个特殊问题在通用开发人员的面试中相当奇怪。
与许多面试问题一样，面试官可能不是在寻求特定的解决方案，而是为候选人提供了一个机会来展示他/她表达各种方法的一般利弊的能力。此外，如果候选人有机会在回复之前查找通用资源，例如 MathWorld 或 Wikipedia，这也可能是对他/她快速理解那里提供的信息的能力的一个很好的测试。

于 2011-07-04T04:15:24.090 回答
0

这是一个快速的算法，只是为了好玩，在 PHP 中 - 只使用一个简单的for循环。您可以轻松地将其移植到其他语言：

function isPerfectNumber($num) {
        $out = false;

        if($num%2 == 0) {
            $divisors = array(1);
            for($i=2; $i<$num; $i++) {
                if($num%$i == 0)
                    $divisors[] = $i;
            }

            if(array_sum($divisors) == $num)
                $out = true;
        }

        return $out ? 'It\'s perfect!' : 'Not a perfect number.';
    }

希望这会有所帮助，不确定这是否是您要找的。

于 2011-07-04T03:29:12.927 回答
0 
#include<stdio.h>
#include<stdlib.h>
int sumOfFactors(int ); 

int main(){
int x, start, end;
    printf("Enter start of the range:\n");
    scanf("%d", &start);
    printf("Enter end of the range:\n");
    scanf("%d", &end);

    for(x = start;x <= end;x++){
        if(x == sumOfFactors(x)){
            printf("The numbers %d is a perfect number\n", x);
        }
    }   
    return 0;
}

int sumOfFactors(int x){
    int sum = 1, i, j;
    for(j=2;j <= x/2;j++){
        if(x % j == 0)
            sum += j;
    }
    return sum;
}
于 2016-07-30T04:55:43.497 回答