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

我正在编写一个非常简单的程序来检查一个数字是否可以均匀地划分另一个数字：

// 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 

用于测试分频器是否可以均匀划分数字，除了使用％之外还有更有效的方法进行测试吗？

Answer 1

我不打算解决查找整数所有因子的最佳算法。 相反，我想评论你当前的方法。

有条件测试案例需要考虑

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

有关更多详情，请参阅试验部门的普通性条件测试 。

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

案例1的优点是它不需要分割。 但是，当divider*divider大于最大整数时，它可能会溢出。 案例二没有溢出问题，但需要划分。 对于case3， sqrt只需要计算一次，但它要求sqrt函数得到正确的正方形。

但是还有其他东西需要考虑许多指令集，包括x86指令集，在进行除法时也会返回余数。 由于你已经在使用number % divider这意味着你在进行number / divider时可以免费获得它。

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

在案例2和案例3之间，我认为主要问题是指令集。 如果sqrt与case2相比太慢，或者如果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指令集的最佳选择。

Answer 2

但是，似乎sqrt（）实际上无法提高效率

这是可以预料的，因为每次迭代的保存乘法很大程度上由循环内慢得多的除法运算决定。

此外， number % divider = 0用于测试分频器是否可以均匀划分数字，除了使用％之外还有更有效的方法进行测试吗？

从来没听说过。 检查a % b == 0是否至少与检查某些c a % b = c一样困难，因为我们可以使用前者计算后者（添加一个额外的）。 至少在英特尔架构上，计算后者的计算成本与分区一样昂贵，这是典型的现代处理器中最慢的操作。

如果你想要更好的性能，你需要一个更好的分解算法，其中有很多 。 运行时O（n ^1/4 ）的一个特别简单的是Pollard的ρ算法 。 您可以在我的算法库中找到简单的C ++实现。 对C的改编留给读者练习：

 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& facts) { if (n == 1) return; if (rabin(n)) { // simple randomized prime test (eg Miller–Rabin) // we found a prime factor facts[n]++; return; } int f = rho(n); factor(n/f, facts); factor(f, facts); } 

从其素因子构造n因子是一项容易的任务。 只需将所有可能的指数用于找到的素数因子，并以各种可能的方式将它们组合起来。

Answer 3

在C中，您可以使用头文件的sqrt()函数系列来获取浮点数的sqrt() 。

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

但是，如果算法改进很好，那么sqrt()调用的速度稍慢通常无关紧要。

要仅比较number平方根，请使用以下代码：

 #include  /* ... */ 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 4

这只是我随意的想法，所以如果它错了，请评论并批评它。

这个想法是预先计算低于特定范围的所有素数并将其用作表格。

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

最后，结果是输入的所有主要因素及其计数的表格。 然后产生所有的自然因素应该是琐事，不是吗？

最坏的情况是，循环需要结束，然后需要6542次迭代。

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

这是实现此方法的MATLAB代码：

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

 function [ output_non_zero ] = fact2(input, p) output_table=zeros(size(p)); i=1; while(i 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');