5

链接：http ://projecteuler.net/problem=23

完美数是一个数，其真因数之和正好等于该数。例如，28 的真因数之和为 1 + 2 + 4 + 7 + 14 = 28，这意味着 28 是一个完美数。

一个数 n 如果其真因数之和小于 n 则称为不足数，如果该数之和超过 n 则称为丰富数。

由于 12 是最小的丰度数，1 + 2 + 3 + 4 + 6 = 16，所以可以写成两个丰度数之和的最小数是 24。通过数学分析，可以证明所有大于28123 可以写成两个丰富数之和。但是，即使已知不能表示为两个丰富数之和的最大数小于该上限，也无法通过分析进一步降低该上限。

找出所有不能写成两个丰富数之和的正整数之和。

问题的答案是4179871，我的程序显示3797954。

首先，我创建了一个函数，用 28124 以下的所有丰富数字填充数组丰富[]。这非常好，因为我搜索了丰富的数字，它们与我的数组完全匹配。

其次，我有另一个包含所有数字 1-28123 的数组，我假设所有这些“不能写成两个丰富数字的总和”。这些都被写入数组hold[]。

最后，我去掉了可以写成两个丰富数字之和的数字，方法是将丰富[]中的所有数字与丰富[]中的所有数字相加，并将保持[]的值设置为0。（保持[丰富[0 to n]+abundant[0 to n]] = 0) 把所有剩余的数加到hold[]中，我只得到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) == 0并不意味着它sqrt(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 回答
0 
my_set = set([i for i in range(1, 28123)])
print ('original sum',sum(my_set))
my_list = list(my_set)
my_l1 =[]
for k in range(12, int(my_list[-1]/2+1)):
    a = 0
    for j in range(1, int(k/2+1)):
        if k%j == 0:
            a += j
        
    if a > k:
        my_l1.append(k)
        my_set.remove(k*2)
#Calculating the sum of all the numbers which can be written as the sum of two abundant numbers   
l = 0
my_l2 = set([])
for d in my_l1:
    l += 1
    k = l
    while k < len(my_l1):
        a_s = d + my_l1[k]
        my_l2.add(a_s)
        k += 1
my_set.difference_update(my_l2)
print ('sum of all abbundant numbers:',sum(my_set))

这是我的problem23 Project Euler的代码，这有什么问题？我现在不关心运行时，我只想要正确的答案。

Python

于 2014-11-26T02:33:47.770 回答