找到整数的所有因子的有效算法是什么? [英] What is an efficient algorithm to find all the factors of an integer?

问题描述

我正在编写一个非常简单的程序，以检查一个数字是否可以将另一个数字平均除:

I was writing a very simple program to examine if a number could divide another number evenly:

// 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()并不能真正提高效率. sqrt()如何在C中处理，如何提高sqrt()的效率?另外，还有其他方法可以更有效地解决问题吗?

Now I was curious if the task could be done by finding the square root of number and compare it to divider. However, it seems that sqrt() isn't really able to boost the efficiency. How was sqrt() handled in C and how can I boost the efficiency of sqrt()? Also, is there any other way to approach the answer with even greater efficiency?

此外，

number % divider == 0

用于测试除法器是否可以平均除数，除了使用％之外，还有一种更有效的测试方法吗?

is used to test if divider could evenly divide number, is there also a more efficient way to do the test besides using %?

推荐答案

我将不讨论查找整数的所有因子的最佳算法.相反，我想评论一下您当前的方法.

I'm not going to address what the best algorithm to find all factors of an integer is. Instead I would like to comment on your current method.

有一些条件测试案例要考虑

There are thee conditional tests cases to consider

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

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

有关更多详情，请参见按试法划分的素数条件测试

See Conditional tests in primality by trial division for more detials.

要使用的情况取决于您的目标和硬件.

The case to use depends on your goals and hardware.

情况1的优点在于它不需要除法.但是，当divider*divider大于最大整数时，它可能会溢出.情况二没有溢出问题，但是需要除法.对于case3，sqrt只需要计算一次，但是它要求sqrt函数正确地求出完美平方.

The advantage of case 1 is that it does not require a division. However, it can overflow when divider*divider is larger than the largest integer. Case two does not have the overflow problem but it requires a division. For case3 the sqrt only needs to be calculated once but it requires that the sqrt function get perfect squares correct.

但是还有很多其他的指令集需要考虑，包括x86指令集，在进行除法运算时也会返回余数.由于您已经在执行number % divider，这意味着您在执行number / divider时可以免费获得它.

But there is something else to consider many instruction sets, including the x86 instruction set, return the remainder as well when doing a division. Since you're already doing number % divider this means that you get it for free when doing number / divider.

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

Therefore, case 1 is only useful on system where the division and remainder are not calculated in one instruction and you're not worried about overflow.

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

Between case 2 and case3 I think the main issue is again the instruction set. Choose case 2 if the sqrt is too slow compared to case2 or if your sqrt function does not calculate perfect squares correctly. Choose case 3 if the instruction set does not calculate the divisor and remainder in one instruction.

对于x86指令集，情况1，情况2和情况3应该具有基本相同的性能.因此，应该没有理由使用案例1(但是请在下面看到一个微妙的要点). C标准库保证正确完成完美平方的sqrt.因此，情况3也没有缺点.

For the x86 instruction set case 1, case 2 and case 3 should give essentially equal performance. So there should be no reason to use case 1 (however see a subtle point below) . The C standard library guarantees that the sqrt of perfect squares are done correctly. So there is no disadvantage to case 3 either.

但是情况2有一个微妙的要点.我发现有些编译器无法识别除法和余数是一起计算的.例如下面的代码

But there is one subtle point about case 2. I have found that some compilers don't recognize that the division and remainder are calculated together. For example in the following code

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

即使只需要一条指令，GCC也会产生两条除法指令.解决此问题的一种方法是像这样保持分隔和提醒紧密

GCC generates two division instruction even though only one is necessary. One way to fix this is to keep the division and reminder close like this

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具有相同的性能.但是，这段代码比

In this case GCC produces only one division instruction and case1, case 2 and case 3 have the same performance. But this code is a bit less readable than

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

因此，我认为总体情况3至少对于x86指令集是最佳选择.

so I think overall case 3 is the best choice at least with the x86 instruction set.

这篇关于找到整数的所有因子的有效算法是什么?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！