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

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

在 C 语言中，您可以使用 header <math.h>.

中的 sqrt() 函数族对浮点数求平方根

求平方根通常比除法慢，因为求平方根的算法比除法算法复杂。这不是 C 语言的属性，而是执行程序的硬件。在现代处理器上，求平方根和除法一样快。例如，这适用于 Haswell 微架构。

然而，如果算法改进良好，sqrt() 调用速度稍慢通常无关紧要。

要只比较 number 的平方根，请使用如下代码：

#include <math.h>

/* ... */

int root = (int)sqrt((double)number);
for(divider = 2; divider <= root; divider++)
    if(number % divider = 0)
        print("%d can divided by %d\n", number, divider);

Answer 2

However, it seems that sqrt() isn't really able to boost the efficiency

这是意料之中的，因为每次迭代节省的乘法运算主要由循环内慢得多的除法运算决定。

Also, the 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 %?

据我所知没有。检查 a % b == 0 是否至少与检查某些 c 的 a % b = c 一样困难，因为我们可以使用前者来计算后者（需要额外添加）。至少在 Intel 架构上，计算后者的计算成本与除法一样高，这是典型的现代处理器中最慢的操作之一。

如果你想要显着更好的性能，你需要更好的因式分解算法，其中there are plenty. One particular simple one with runtime O(n^1/4) is Pollard's ρ algorithm. You can find a straightforward C++ implementation in my algorithms library。对 C 的适应留作 reader:

的练习

int rho(int n) { // will find a factor < n, but not necessarily prime
  if (~n & 1) return 2;
  int c = rand() % n, x = rand() % n, y = x, d = 1;
  while (d == 1) {
    x = (1ll*x*x % n + c) % n;
    y = (1ll*y*y % n + c) % n;
    y = (1ll*y*y % n + c) % n;
    d = __gcd(abs(x - y), n);
  }
  return d == n ? rho(n) : d;
}

void factor(int n, map<int, int>& facts) {
  if (n == 1) return;
  if (rabin(n)) { // simple randomized prime test (e.g. Miller–Rabin)
    // we found a prime factor
    facts[n]++;
    return;
  }
  int f = rho(n);
  factor(n/f, facts);
  factor(f, facts);
}

从质因数构造 n 的因数是一件容易的事。只需使用找到的主要因素的所有可能指数，并以各种可能的方式组合它们。

Answer 3

这只是我的胡思乱想，如有不妥请大家指正。

想法是预先计算出一定范围内的所有质数，并将其用作table。

循环通过 table，检查素数是否是一个因子，如果是，则增加该素数的计数器，如果不是，则增加索引。当索引到达末尾或要检查的质数超过输入时终止。

最后，结果是输入的所有质因子及其计数的 table。那么生成所有自然因素应该是微不足道的，不是吗？

最坏的情况，循环需要走到尽头，然后需要6542次迭代。

考虑到输入是 [0, 4294967296] 这类似于 O(n^3/8)。

下面是实现此方法的 MATLAB 代码：

如果 p 由 p=primes(65536); 生成，则此方法适用于 [0, 4294967296] 之间的所有输入（但未测试）。

function [ output_non_zero ] = fact2(input, p)
    output_table=zeros(size(p));
    i=1;
    while(i<length(p));
        if(input<1.5)
            break; 
            % break condition: input is divided to 1,
            % all prime factors are found. 
        end
        if(rem(input,p(i))<1)
            % if dividable, increament counter and don't increament index
            % keep checking until not dividable
            output_table(i)=output_table(i)+1;
            input = input/p(i);
        else
            % not dividable, try next
            i=i+1;
        end
    end

    % remove all zeros, should be handled more efficiently
     output_non_zero = [p(output_table~=0);...
                        output_table(output_table~=0)];
     if(input > 1.5)
         % the last and largest prime factor could be larger than 65536
         % hence would skip from the table, add it to the end of output
         % if exists
         output_non_zero = [output_non_zero,[input;1]];
     end
end

测试

p=primes(65536);
t = floor(rand()*4294967296);
b = fact2(t, p);
% check if all prime factors adds up and they are all primes
assert((prod(b(1,:).^b(2,:))==t)&&all(isprime(b(1,:))), 'test failed');

Answer 4

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

有条件测试用例需要考虑

(divider * divider) <= number
divider <= number/divider
divider <= sqrt(number)

有关详细信息，请参阅 Conditional tests in primality by trial division。

具体使用情况取决于您的目标和硬件。

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

但是还有一些其他的东西需要考虑很多指令集，包括 x86 指令集，return 做除法时还有余数。因为你已经在做 number % divider 这意味着你在做 number / divider.

时免费获得它

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

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

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

What is an efficient algorithm to find all the factors of an integer?

c

algorithm

math

primes

square-root