c - 找到整数的所有因子的有效算法是什么？

Question

我正在编写一个非常简单的程序来检查一个数是否可​​以整除另一个数:

// use the divider squared to reduce iterations
for(divider = 2; (divider * divider) <= number; divider++)
    if(number % divider == 0)
        print("%d can divided by %d\n", number, divider);

现在我很好奇是否可以通过找到数字的平方根并将其与除法器进行比较来完成该任务。但是，似乎 sqrt() 并不能真正提高效率。在 C 中如何处理 sqrt() 以及如何提高 sqrt() 的效率？另外，有没有其他方法可以更高效地接近答案？

此外，

number % divider == 0

用来测试divider是否能均分数，除了%还有其他更高效的测试方法吗？

Answer 1

我不打算讨论找出整数所有因数的最佳算法是什么。相反，我想对您当前的方法发表评论。

有条件测试用例需要考虑

1. (divider * divider) <= number
2. divider <= number/divider
3. divider <= sqrt(number)

参见 Conditional tests in primality by trial division了解更多详情。

使用哪种情况取决于您的目标和硬件。

情况1的优点是不需要除法。但是，当 divider*divider 时它会溢出大于最大整数。情况二不存在溢出问题，但需要除法。对于案例 3 sqrt只需要计算一次，但需要 sqrt函数得到完美的正方形。

但是还有一些其他的东西需要考虑很多指令集，包括 x86 指令集，在做除法时也会返回余数。因为你已经在做 number % divider这意味着您在执行 number / divider 时免费获得它.

因此，情况 1 仅适用于不在一条指令中计算除法和余数且您不担心溢出的系统。

在案例 2 和案例 3 之间，我认为主要问题还是指令集。如果 sqrt 选择案例 2与案例 2 相比太慢，或者如果您的 sqrt函数不能正确计算完全平方。如果指令集不在一条指令中计算除数和余数，则选择情况3。

对于 x86 指令集情况 1、情况 2 和情况 3 应该提供基本相同的性能。因此，应该没有理由使用案例 1(但请参阅下面的细微之处)。 C 标准库保证 sqrt的完美正方形正确完成。所以情况 3 也没有缺点。

但是关于案例 2 有一个微妙的地方。我发现一些编译器不承认除法和余数是一起计算的。例如在下面的代码中

for(divider = 2; divider <= number/divider; divider++)
    if(number % divider == 0)

GCC 生成两条除法指令，即使只需要一条。解决此问题的一种方法是像这样关闭分区和提醒

divider = 2, q = number/divider, r = number%divider
for(; divider <= q; divider++, q = number/divider, r = number%divider)
    if(r == 0)

在这种情况下，GCC 只产生一个除法指令，并且 case1、case 2 和 case 3 具有相同的性能。但是这段代码的可读性比

差一点

int cut = sqrt(number);
for(divider = 2; divider <= cut; divider++)
    if(number % divider == 0)

所以我认为总体情况 3 至少是 x86 指令集的最佳选择。