Euler 23 C++项目

Question

我一直在从事项目Euler #23.

这是一项任务：

问题23 完全数是指它的适当除数之和与其数完全相等的一个数。例如，28的适当除数之和为1+2+4+7+ 14 = 28，这意味着28是一个完美数。 如果一个数n的适当除数之和小于n，则称为亏，如果这个数大于n，则称它为富足数。 由于12是最小的富足数，1+2+3+4+6= 16，可以写成两个富足数之和的最小数是24。通过数学分析，可以证明所有大于28123的整数都可以写成两个丰富数的和。然而，这个上限不能通过分析进一步减少，即使已知不能表示为两个丰富数之和的最大数小于这个极限。 找出所有正整数的和，这些正整数不能写成两个丰富数的和。

#include<iostream>
using namespace std;

int main() {
    long long sum;
    int numbers[30000];
    int ab[7000];

    for(int i=0;i<7000;i++)
        ab[i]=0;

    //array of numbers
    for(int i=0; i<28123;i++)
        numbers[i]=i+1;

    //abundant numbers
    int abud_counter=0;
    for(int i=1; i<28124;i++){

        //factors
        int temp=0;
        for(int j=2;j<=i/2;j++) {
            if(i%j==0)
                temp=temp+j;
        }
        temp=temp+1;
        if(temp > i) {
            ab[abud_counter]=i;
            numbers[i-1]=0;
            abud_counter=abud_counter+1;

            if(abud_counter>6965)
                break;
        }
    }

    //all shit
    int array2[7000];
    for(int i=0; i<6965; i++)
        array2[i]=ab[i];

    int k=0;
    for(int i=0;i<6965;i++) {
        for(int j=0;j<6965;j++) {
            if(ab[i]+array2[j]==numbers[ab[i]+array2[j]-1]) {
                numbers[ab[i]+array2[j]-1]=0;
            }
        }
    }

    sum=0;
    for(int i=0; i<28123; i++) {
        sum = sum+numbers[i]; 
    }
    cout<<sum;
    return 0;
}

我得到的总价值是4178876。正确的答案是4179871。我花了10个小时查看我的代码，但是我找不到错误。我应该修改什么来纠正错误？我的回答已经接近了。提前感谢

PS。我对学习很陌生。运行时为1.3 s，任何优化都是有用的。

Answer 1

在发布的代码中，除了一些效率低下和滥用神奇数字之外，还存在一些问题。

当填充大量数字的数组时，number数组的某些元素被错误地归零。

if(temp > i) {
    ab[abud_counter]=i;
    numbers[i-1]=0;               // <----- Why? Remove this line.
    abud_counter=abud_counter+1;
    if(abud_counter>6965)
        break;
}

当我尝试这个程序时，由于这一行，我遇到了一个分割错误。

for(int i=0;i<6965;i++) {
    for(int j=0;j<6965;j++) {
        if(ab[i]+array2[j]==numbers[ab[i]+array2[j]-1]) {
            //                      ^^^^^^^^^^^^^^^^^^   
            numbers[ab[i]+array2[j]-1]=0;
        }
    }
}

numbers有30000个元素，但是ab[i]和array2[j]的值都可以高达28123。

顺便说一句，array2是多余的，它只是ab的一个副本。

您的算法的一个修改版本(生成正确的值为4179871 )可以是下面是。

#include <array>
#include <iostream>
#include <vector>

long sum_of_dividends(int n)
{
    long sum{1};
    int i = 2;
    for (int j = n; i < j; ++i)
    {
        if ( n % i == 0 )
        {
            sum += i;
            j = n / i;
            if (i == j)
               break;
            sum += j;
        }
    }
    return sum;
}

int main() 
{
    std::vector<int> abundants;
    abundants.reserve(7000);
    constexpr int max_value = 28123;
    for (int i{1}; i <= max_value; ++i)
    {
        if (sum_of_dividends(i) > i)
            abundants.push_back(i);
    }

    std::array<bool, max_value> are_sums{};

    for (unsigned i{}; i < abundants.size(); ++i)
    {
        for (unsigned j{i}; ; ++j)
        {
            long k = abundants[i] + abundants[j];
            if (k >= max_value)
                break;
            are_sums[k] = true;
        } 
    }
    long sum{};
    for (int i{}; i < max_value; ++i)
        if (!are_sums[i])
            sum += i;

    std::cout << sum << '\n';
}

虽然以前的实现利用了一种更快的方法来计算一个数字的红利之和，但处理时间的戏剧性改进需要一种不同的方法来搜索丰富的数字。

下面的片段利用了一个类似于Eratosthenes筛子的想法，它不是搜索范围内的每个数的分红，而是将适当数目的每个红利相加。

std::vector<int> abundants;
std::vector<long> dividends_sums(max_value + 1, 1);
for (int i{2}; i <= max_value; ++i)
{
    for (int j{i * 2}; j <= max_value; j += i)
        dividends_sums[j] += i;
    if (dividends_sums[i] > i)
        abundants.push_back(i);
}

这种修改的影响可以看到这里。