查找 'quite good' 最多 100 万个数字的最佳方法？

Question

我正在做一项涉及 'quite good' 个数字的作业。该任务将它们描述为：

“一个“相当好”的数字是一个整数，其“坏度”——其除数之和与数字本身之间的差值——不大于指定值。例如，如果最大值badness 设置为 3，有 12 个小于 100 的“相当好”的数字：2、3、4、6、8、10、16、18、20、28、32 和 64；你的任务是编写一个 C++程序，quitegood，确定小于指定值的指定最大不良数。执行程序时，将限制值和最大不良指定为命令行参数。"

该任务要求我编写一个程序，打印指定坏数上限为一百万的完美数字。所以，命令行参数 quitegood 1000000 1 应该打印 2 4 6 8 16 28 32 64 128 256 496 512 1024 2048 4096 8128 8192 16384 32768 65536 131072 262144 524288.

我已将其与以下代码一起使用

#include <iostream>

using namespace std;

int main(int argc, char *argv[]) {

    const int limit = argc > 1 ? atoi(argv[1]) : 1000000;
    const int badness = argc > 2 ? atoi(argv[2]) : 10;

    for(int number = 2; number < limit; number++) {
        int sum = 1;
        for (int factor = 2; factor < number; factor++){
            if (number % factor == 0) {
                sum += factor;
            }
        }

        if (number >= (sum - badness) && number <= (sum + badness)) {
            cout << number << " ";
        }
    }

    return 0;
}

唯一的问题是此代码查找 'quite good' 高达 100 万的数字太慢了。有什么优化方法吗？

谢谢

Answer 1

如果 f 是 n 的因数，那么 n/f 也是（尽管当 f 是 n 的平方根时，f 和 n/f 是同一个因数）。因此，您可以通过仅计算 sqrt(number) 以内的因子来使代码更快，然后当您找到一个因子时还包括匹配因子 number/factor（平方根情况除外）。

for (int factor = 2; factor * factor <= number; factor++){
    if (number % factor == 0) {
        sum += factor;
        if (factor * factor != number) {
            sum += number / factor;
        }
    }
}

在 limit 为 100 万且 badness 1. 等待原始代码完成几分钟后，我感到无聊。

为了使代码更快，您可以找到数字的质因数分解，并使用 formula for the sum of the divisors based on the prime factorization.

即使不预先计算素数，使用此方法在我的机器上也能在 0.713 秒内运行。这是我从 number:

计算 sum 的代码

int n = number;
int i = 2;
while (n > 1) {
    if (i * i > n) {
        sum *= (n + 1);
        break;
    }
    int pp = i;
    while (n % i == 0) {
        pp *= i;
        n /= i;
    }
    sum *= (pp - 1) / (i - 1);
    i += 1;
}
sum -= number;

它找到除以 number 的所有质数幂，并且对于每个 p^m 将 sum 乘以 (p^(m+1) - 1) / (p - 1) .与第一个解决方案一样，它在 i*i > n 时提前停止，这意味着 n 是素数。

在一般情况下，它比第一个解决方案快很多，因为虽然我们仍在进行试除，但 n 会随着找到质因数而变小。

如果你已经预先计算了足够大的素数列表（也就是说，它至少包括一个大于极限的平方根的素数），你可以在计算 sum 时再次提高效率：

int n = number;
for (int i = 0; primes[i] * primes[i] <= n; ++i) {
    int pp = primes[i];
    while (n % primes[i] == 0) {
        pp *= primes[i];
        n /= primes[i];
    }
    sum *= (pp - 1) / (primes[i] - 1);
}
if (n > 1) sum *= (n + 1);
sum -= number;

采用这种计算方式的代码 sum 在我的机器上运行时间为 0.189 秒。

查找 'quite good' 最多 100 万个数字的最佳方法？

Best way to find 'quite good' numbers up to 1 million?

c++

algorithm

math

c++11

perfect-numbers