c++ - 使循环更快

Question

我想计算一个数字是否是一个完美的数字(总和(适当的除数)== 数字)。所以我所要做的就是得到合适的除数，将它们相加并查看它是否是数字。为此，我使用了一个 for 循环:

cin >> number;
sum = 1;
for (int i = number/2; i > 1; --i) {
  if (number % i == 0) {
    sum = sum + i;
  }
  if (sum > number) {break;}
}
if (sum == number) {cout << "perfect!" << endl;}

这个循环太慢了。如你所见，我已经完成的是，如果总和已经大于数字，我就跳出循环，我从更高的数字开始(所以如果总和更大，它到达那里的速度更快)，因为 1 总是适当的除数，我不需要遍历它。

现在我有点想不通了，我真的很感激一些关于如何进一步改进这个循环的技巧(或者甚至是一种完全不同的方法？)

Answer 1

您可以通过以下方式获得非常大的改进:

cin >> number;
sum = 1;
for (int i = sqrt(number); i > 1; --i) {
  if (number % i == 0) {
    sum += i + (number / i);
  }
  if (sum > number) {break;}
}
if (sum == number) {cout << "perfect!" << endl;}

如您所见，此循环从输入的平方根开始，而不是输入的一半。这在最坏的情况下提供了 O(sqrt(N)) 改进。对于任何一对数的除数，一个必须位于平方根之上，一个必须位于平方根之下。另一个需要注意的重要事情是整数除法/模数非常昂贵，但是当计算它们时，两者是同时计算的。这意味着一旦您计算了 number % i，number/i 基本上是免费的。因此，我的代码中每次迭代的成本与您代码中的每次迭代成本基本相同，但迭代次数要少得多。

如果你这样做，你可能还想考虑向上计数而不是向下计数，如果你的目标是提前退出，那么一般来说你最好从小数开始，因为更多的极值除数(一个非常高，一个非常低)更大。此外，数字越小，除数的密度就越高。

请注意，我的代码并不完全正确，需要考虑一些边缘情况，完美正方形就是一个例子。