c - 如何使用平方根优化c中的循环(完美、丰富、不足)

Question

注意:我遗漏了不相关的代码

所以我目前正在研究 CCC 1996 P1，这个问题的全部目的是能够计算一个整数输入是完美数、不足数还是充数。我上面列出的代码可以工作，但是我认为它太慢了。该代码会迭代每个数字以找到完美的除数，我认为这效率太低了。不管怎样，我已经考虑这个问题有一段时间了，但似乎想不出任何方法来优化这段代码。

我在网上读到，您可以将 i < n 替换为 i < sqrt(n)，然后将分数添加到 s += i + (n/i) 或类似的行切换，这似乎对我不起作用。关于我可以采取哪些措施来获得更高效的代码并减少运行时间的任何建议，因为目前，程序在达到输出之前运行的时间太长。任何帮助将不胜感激，谢谢!

此外，如果一个数字的所有完美除数之和等于该数字，则该数字被定义为完美数字。如果一个数的所有完美除数之和 > 该数，则该数被定义为丰富的。如果一个数的所有完美除数之和<该数，则该数被定义为不足数。该数字本身不算是完美除数。

我不太熟悉 Big-O 表示法。

此外，如果一个数字的所有完美除数之和等于该数字，则该数字被定义为完美数字。如果一个数的所有完美除数之和 > 该数，则该数被定义为丰富的。如果一个数的所有完美除数之和<该数，则该数被定义为不足数。该数字本身不算是完美除数。

Answer 1

你应该更换

score += i + ((sqrt(numInput))/i);

与

result = numInput/i;
score += (result == i || i == 1)? i : i + result;

这个想法是，对于每个小于平方根的因子，结果总是大于或等于平方根，并且也是一个因子。