计算给定数量的除数数的算法

Question

计算给定数量的除数数的算法

计算给定数量的除数的最佳算法（性能方面）是什么？

如果您能提供伪代码或链接到一些示例，那将会很棒。

编辑：所有答案都非常有帮助，谢谢。我正在实施Atkin的Sieve，然后我将使用类似于Jonathan Leffler所指出的东西。Justin Bozonier发布的链接提供了我想要的更多信息。

Answer 1

你的除数函数有一个错误，因为它对于完美的正方形不能正常工作。尝试：int&nbsp;divisors(int&nbsp;x)&nbsp;{ &nbsp;&nbsp;&nbsp;&nbsp;int&nbsp;limit&nbsp;=&nbsp;x; &nbsp;&nbsp;&nbsp;&nbsp;int&nbsp;numberOfDivisors&nbsp;=&nbsp;0; &nbsp;&nbsp;&nbsp;&nbsp;if&nbsp;(x&nbsp;==&nbsp;1)&nbsp;return&nbsp;1; &nbsp;&nbsp;&nbsp;&nbsp;for&nbsp;(int&nbsp;i&nbsp;=&nbsp;1;&nbsp;i&nbsp;<&nbsp;limit;&nbsp;++i)&nbsp;{ &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;if&nbsp;(x&nbsp;%&nbsp;i&nbsp;==&nbsp;0)&nbsp;{ &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;limit&nbsp;=&nbsp;x&nbsp;/&nbsp;i; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;if&nbsp;(limit&nbsp;!=&nbsp;i)&nbsp;{ &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;numberOfDivisors++; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;} &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;numberOfDivisors++; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;} &nbsp;&nbsp;&nbsp;&nbsp;} &nbsp;&nbsp;&nbsp;&nbsp;return&nbsp;numberOfDivisors;}