小于或等于 n 的所有丰富数字的总和

Question

问题是求出所有小于或等于 n 的丰度数之和，其中丰度数是一个数，其所有适当因子的和大于该数，例如。 12 是一个丰富的数字，因为
1 + 2 + 3 + 4 + 6 = 16 大于 12。

这是我的实现，我正在获取 TLE，我被困在这里似乎找不到任何方法。请帮忙。

int isAbundant(int n){
int sum = 0;
for (int i=1; i<=sqrt(n); i++){
    if (n%i==0){
        if (n/i == i)
            sum = sum + i;

        else{
            sum = sum + i;
            sum = sum + (n / i);
        }
    }
}
if(sum - n > n) return 1;
else            return 0;
}

int find_abundant_numbers(int n1) {

set<int> s;

if(n1 < 12)  return 0;

for(int i = 12; i <= n1; i++){
    if(i % 2 != 0 && i < 945){
        continue;
    }
    if(s.find(i) == s.end()){
        int isA = isAbundant(i);
        if(isA){
            for(int j = 1; j * i <= n1; j++){
                s.insert(i * j);
            }
        }
    }
    else{
        continue;
    }
    //if(isA) cout << isA << " ";
}

return accumulate(s.begin(), s.end(), 0);
}

Answer 1

你的问题是找到set个小于n的个数，而不是检查一个个特定的数是否很多。以 Eratosthenes 的筛法为例，这是一种古老的算法，用于查找小于给定数的所有素数。它不会一个一个地检查一个数是否是质数，而是在更高的水平上更有效地工作，在一系列数字上。

想法是有一个数组 std::vector<int> sum(n + 1);（最初所有值都设置为 0），它被递增填充，直到我们获得 all[=31= 所需的严格除数之和] 数字。给定一个值（除数），子进程将更新数组 sum，方法是将此值添加到 sum 中表示可被它整除的数字的所有元素（严格）：

auto propagate_divisor = [&](int divisor) { for (int i = 2 * divisor; i <= n; i += divisor) sum[i] += divisor; };

然后，我们对所有可能的值执行此操作：

for (int i = 1; i <= n; ++i) propagate_divisor(i);

现在，随着 sum 的构建，我们只需要选择大量的数字（这里，我只是打印它们）：

for (int i = 0; i <= n; ++i) if (sum[i] > i) printf("%i ", i);

You can try it here.

小于或等于 n 的所有丰富数字的总和

sum of all abundant numbers less than or equal to n

c++

optimization

mathematical-optimization