5

リンク : http://projecteuler.net/problem=23

完全数とは、その固有約数の合計がその数と正確に等しい数です。たとえば、28 の適切な約数の合計は 1 + 2 + 4 + 7 + 14 = 28 になります。つまり、28 は完全数です。

固有約数の合計が n 未満の場合、数 n は不足と呼ばれ、この合計が n を超える場合、数 n は豊富と呼ばれます。

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

2 つの豊富な数の合計として書ききれないすべての正の整数の合計を求めます。

問題の答えは 4179871 で、私のプログラムは 3797954 を示しています。

何よりもまず、配列豊富な [ ] を 28124 未満のすべての豊富な数字で埋める関数を作成します。豊富な数字をグーグル検索したところ、配列と正確に一致するため、これは完全に正常に機能します。

次に、すべての数字が 1 ～ 28123 の別の配列があります。それらすべてが「2 つの豊富な数字の合計として記述できない」と仮定します。これらはすべて配列 hold[ ] に書き込まれます。

最後に、豊富な [ ] 内のすべての数値と豊富な [ ] 内のすべての数値を加算し、ホールド [ ] の値を 0 に設定することにより、2 つの豊富な数値の合計として記述できる数値を取り除きます。豊富な[0からn] +豊富な[0からn]] = 0)ホールド[]に残りのすべての数字を追加すると、3797954しか得られません

このプログラムは、すべての豊富な数にすべての豊富な数を加算するため、あまり効率的ではないことはわかっていますが、問題なく動作するはずです。どうしたの？

#include <iostream>
#include <cmath>

using namespace std;

int hold[28124];
int abundant[7000]; //hold abundant numbers, there are only 6919 abundant numbers below 28123

bool abundance(int x){  //returns true if x is abundant
    int counter = 1;    //holds "proper divisors" of numbers, default by 1 because every int is divisible by 1
    for (int i = 2; i < sqrt(x); i++){   //finds all divisors 2 - sqrt(n)
        if (x % i == 0){
            counter += i;
            counter += x / i;
        }
    }
    int y = sqrt(x);   
    if (x % y == 0){   //adds sqrt(n) if its modulus to n is 0
            counter += sqrt(x);
        }
    if (counter > x){
        return true;
    } else {
        return false;
    }
}

int main()
{
    int counter = 0;
    for (int i = 0; i < 28124; i++){ //assumes every number cannot be written as the sum of two abundant numbers,
        hold[i] = i;                 //goes up to 28123 because "it can be shown that all integers greater
    }                                //than 28123 can be written as the sum of two abundant numbers." - project euler
    for (int j = 10; j < 28124; j++){ 
        if (abundance(j) == true){  //copies all abundant numbers up to 28123 to abundant[]
            abundant[counter] = j;
            counter++;
        }
    }

    for (int m = 0; m < counter; m++){  //adds all numbers in abundant[], with all numbers in abundant[]
        for (int n = 0; n < counter; n++){
            if (abundant[m]+abundant[n] < 28124){
                hold[abundant[m]+abundant[n]] = 0; //sum of the abundant numbers in hold[] is set to 0
            } //hold[] now holds all numbers that cannot be written as the sum of 2 abundant numbers
        }
    }
    int counter2 = 0;
    for (int x = 0; x < 28124; x++){
        counter2 += hold[x];
    }
    cout << counter2 << endl;

}
4

3 に答える 3

7

問題はあなたのabundance機能、特にこの部分にあります:

int y = sqrt(x);   
if (x % y == 0){   //adds sqrt(n) if its modulus to n is 0
    counter += sqrt(x);
}

x % (int)sqrt(x) == 0sqrt(x)が整数であることを意味しません。簡単な反例は 2です。sqrt(2)は約1.414、またはちょうど1整数です。でも2 % 1 == 0、平方根じゃないのに。

コードを修正するには、その部分を次のように変更します。

int y = sqrt(x);   
if (y * y == x){   //adds sqrt(n) if sqrt(n) is an integer
    counter += y;
}

そして、正しい結果が得られます。

于 2013-04-21T06:31:16.273 に答える
1

正しい答えが得られたという理由だけで、ここに示されているコードを見てください。そこで行われたことをコピーしなくても、たとえば、問題が豊富な数のジェネレーターにあるのか、他の部分にあるのかを確認できます。どこが間違っているのかを理解するのに役立つかもしれません。

于 2013-04-21T06:04:31.800 に答える