找到100万以上“相当好”数字的最佳方法？

Question

我正在做一项涉及“相当好”数字的作业。任务将其描述为：

“相当好”的数字是一个整数，其“坏”——其除数之和与数字本身之差的大小——不大于指定值。例如，如果最大坏值设置为3，则有12个“相当好”小于100的数字：2、3、4、6、8、10、16、18、20、28、32和64；您的任务是编写一个C程序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;
}

唯一的问题是，这段代码太慢，无法找到高达100万的“非常好”数字。有什么方法可以优化这一点吗？

谢谢你

Answer 1

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

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

如果limit为100万，并且badness1，则此代码在我的机器上以1.554s的速度运行。在等待原始代码完成几分钟后，我觉得很无聊。

为了使代码更快，您可以找到数字的质因式分解，并使用基于质因式分解的除数之和公式。

即使不预先计算素数，使用这种方法在我的机器上也能以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^（m1）-1）/（p-1）。与第一个解决方案一样，当i*i时，它会提前停止

在一般情况下，它比第一个解决方案快得多，因为尽管我们仍在进行试验分割，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;

在我的机器上，以这种方式计算总和的代码运行时间为0.189秒。