找到高达 100 万'quite good'数字的最佳方法？

Question

我正在做一项涉及"相当好的"数字的作业。任务将它们描述为:

"A "相当不错"Number是一个"坏"的整数。-其除数之和与数字本身之差的大小-不大于指定值。例如，如果最坏设置为3，则有12个"相当好";小于100的数字:2、3、4、6、8、10、16、18、20、28、32和64;你的任务是写一个c++程序，很好，确定一个指定的最大坏值小于指定值的数字。当程序执行时，限制值和最大坏值作为命令行参数指定。">

这个任务要求我编写一个程序，在指定的坏值限制下输出完全数，最高可达一百万。所以，的命令行参数非常好，10000001应该打印2 4 68 16 28 32 64 128 256 496 512 1024 2048 4096 8128 8192 16384 32768 65536 131072262144 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(数字)来使代码更快，然后当您找到一个时，还包括匹配的因子数/因子(除平方根情况外)。

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

这段代码在我的机器上以1.554运行，limit为100万，badness为1。等待原始代码完成几分钟后，我感到无聊。

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

即使没有预先计算质数，使用此方法在我的机器上运行的时间为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随着质因数的发现而变小。

如果您已经预先计算了一个足够大的素数列表(也就是说，它至少包含一个大于limit的平方根的素数)，那么您可以在计算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秒。