プロジェクトオイラー＃23

Question

は、私は現在のプロジェクトのオイラーの問題番号23を解決しようとしている：

完全数は、その適切な約数の合計が数と正確に一致しているため数です。例えば、28の適切な約数の和は、1 + 2 + 4 + 7 + 14 = 28であり、これは28が完全な数であることを意味する。

数Nその適切約数の和が、N未満であり、この合計がnを超えた場合、それが豊富で呼び出された場合、欠損と呼ばれます。

12は、1 + 2 + 3 + 4 + 6 = 16の最小の豊富な数であり、2つの豊富な数の合計として書くことができる最小の数は24です。数学的分析により、 28123より大きいすべての整数は、2つの豊富な数の合計として記述することができます。ただし、2つの豊富な数の和で表現できない最大の数がこの制限よりも小さいことがわかっていても、この上限を分析することで、これ以上の低減はできません。

は2つの過剰数の和として記述することはできませんすべての正の整数の合計を検索します。

しかし、私のコードは完全にうまくいくようですが、正しい結果が得られません。私は十分な数より多くを計算していますか？

private static void Main() 
    { 
     List<int> AbudantNumbers = new List<int>(); 
     long sum = 0; 
     for (int i = 12; i <= 28123; i++) 
     { 
      int abudantNumber = GetProperDivisor(i); 
      if (abudantNumber > i) 
      { 
       AbudantNumbers.Add(i); 
      } 
     } 

     for (int k = 1; k <= 28123; k++) 
     { 
      int count = 0; 
      for (int i = 0; i < AbudantNumbers.Count; i++) 
      { 
       count = 0; 
       if (AbudantNumbers[i] > k) 
       { 
        break; 
       } 
       for (int j = i; j < AbudantNumbers.Count; j++) 
       { 
        if (AbudantNumbers[j] > k) 
        { 
         break; 
        } 
        if (AbudantNumbers[i] + AbudantNumbers[j] == k) 
        { 
         count++; 
         break; 
        } 
       } 
      } 
      if (count == 0) 
      { 
       sum += k; 
      } 
     } 
     Console.WriteLine(sum); 
     Console.ReadKey(); 
    } 

    private static int GetProperDivisor(int input) 
    { 
     int sum = 1; 
     for (int i = 2; i <= input/2; i++) 
     { 
      if (input%i == 0) 
      { 
       sum += i; 
      } 
     } 
     return sum; 
    } 

私の結果は次のとおりです。297632990 正しい結果がある：4179871

私のコードに明らかな誤りがないかなり大きな違い。

私の第二のアプローチ：

 for (int k = 1; k <= 28123; k++) 
     { 
      var k1 = k; 
      int count = 
       (from t1 in AbudantNumbers.TakeWhile(t1 => t1 <= k1) let a = t1 select t1).Count(
        t1 => AbudantNumbers.TakeWhile(t => t <= k).Any(t => t1 + t == k)); 
      if (count == 0) 
      { 
       sum += k; 
      } 
     } 

私の考えが28123よりも小さいすべての整数をチェックするよりも、28123よりも、すべての過剰数が少なく入手することです（すべて上記2つの過剰数の合計を持っている）すべての回転よりも、過剰数と最後にチェックもしそうなら、我々は2つの過剰数の合計を持っていないものだけを必要とするので、我々はループから抜け出すabundantNumber1 + abundantNumber2 == currentNumber場合。あなたは現在の数kが2つの過剰数a[i] + a[j]の和であることを見つけたら

Answer 1

、あなたがcountを設定し、j以上内側のループのうち、ループ–から抜け出す、それはです。あなたはまだあなたがcountをリセットするすべての残りi Sを、検討することを意味し

。効果的には、kより小さいか等しい最後の豊富な数値だけを考慮します。 2つの数の合計がこの番号を含んでいる可能性はないので、番号を追加するためのあなたの状態、count == 0は、ほとんどの場合、間違っていることでしょう。

k == a[i] + a[j]が見つかると、2つの最も内側のループから抜け出す必要があります。 C＃がラベルされたループを持っていないようですので、過剰数と引数としてkのリストを取る関数に内部ループをリファクタリングすることが最善です。あなたの条件が満たされた場合は、単にtrueを返すことができます。

迅速な醜い修正として、あなたはjをループ後

if (count) break; 

を追加することができます。

あなたのアプローチは非常に効果的です。豊富な数値すべてに2つのネストされたループを書いて、その合計が28124より小さい場合は、その合計をセットに追加するほうがよいでしょう。次に、セットにない1から28124までのすべての数字を追加します。