8

与えられた数が完全数であるかどうかを見つけるためのアルゴリズムを探しています。

私の頭に浮かぶ最も単純なものは：

  1. 数のすべての要因を見つける
  2. 素因数を取得し（素数の場合は数自体を除く）、それらを合計して完全数かどうかを確認します。

これを行うためのより良い方法はありますか？検索すると、いくつかのEuclidsの動作が見つかりましたが、適切なアルゴリズムが見つかりませんでした。また、このゴルフスクリプトは役に立ちませんでした： https：//stackoverflow.com/questions/3472534/checking-whether-a-number-is-mathematically-a-perfect-number 。

数字などは実際の使用法でキャッシュすることができます[完全な番号がどこで使用されているかはわかりません:)]
しかし、これはインタビューで尋ねられているので、それを最適化する「導出可能な」方法があるはずだと思います。

ありがとう ！

4

4 に答える 4

11

入力が偶数の場合は、、2^(p-1)*(2^p-1)with p、2^p-1primeの形式であるかどうかを確認します。

入力が奇数の場合は、「false」を返します。:-)

詳細については、ウィキペディアのページを参照してください。

（実際には、2500万桁未満の完全数は47しかないため、それらの簡単な表から始めることができます。たとえば、64ビットの数値を使用していると想定できるかどうかインタビュアーに尋ねてください...）

于 2011-07-04T03:50:26.817 に答える
0

編集：ダン、私はインタビューに失敗しました！:-(
「因数分解+除数の列挙+それらの合計」アプローチを改善するためのトリックやヒューリスティックを見つけるための熱心な試みで、9を法として1であることが単に必要であり、確かにatの十分な条件ではないことに気づきませんでした。数（6以外）が完全である...
ええと...平均して9分の1の偶数がこの条件を満たす場合、私のアルゴリズムは確かに数が多すぎる完全数を見つけるでしょう;-)。
自分自身を償還するには、ほとんどの場合、より高価な係数の計算を回避するために、デジタルルートを使用するという提案を維持し、維持しますが、フィルターとしてのみ使用します。

【元々の試み：恥の殿堂】

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））よりも計算コストがはるかに低くなります。したがって、インタビュアーが奇数の「完全ではない」応答に満足する場合、ソリューションは非常に効率的であり、ほとんどのコンピューター言語でコード化可能です。

[2回目と3回目の試み...]

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のコメントを2番目にしています。この特定の質問は、汎用開発者のインタビューのコンテキストではかなり奇妙です。
多くの面接の質問と同様に、面接官は特定の解決策を求めているのではなく、候補者がさまざまなアプローチの一般的な長所と短所を明確にする能力を示す機会を提供している可能性があります。また、候補者が応答する前に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 に答える