[算法优化]如何求一个自然数N的所有因子

btbtbtbtbt

这里因子指的是就是N的所有乘法因子,

24 的乘法因子是
1, 2, 3, 4, 6, 12, 24


**法, 从 1 试探到 N.  n 个循环

优化, 从 1 试探到 Sqrt N, 如果能整除, 可以求出两个.

但是, 有没有更加优化的方法?

比如N是一个超级大的数字,
100000000
实际上, 它的约数也就20来个.
但是要用掉10000个循环.

各位童鞋猛, 过位大侠们, 有没有能令在下拨云见日, 茅塞顿开的?

btbtbtbtbt

NN地, 少写了一个8

cxd2436946

1）先找出质数因子的乘积表达式，比如说20=2*2*5
2）然后把2,2,5进行组合拿到所有的因子：2,5,2*2,2*5,2*2*5，还有1。.
如果你有一个数组记录比如说10000以内的所有质数，第一步会更快。

笨笨雁

同意楼上,质数本身仅能被1或本身整除

btbtbtbtbt

谢谢楼上的楼上, 这个方法我已经试了.

现在我的问题是, 有没有快速的, 把一个数分解成因数的方法?

除了用质数一个一个除的方法.

笨笨雁

可以将一些小的数的因子保存起来,如果一个数能被这个小的数整除,那么小的数的因子也肯定是这个数的因子.

比如24能被 6整除,而6的因子有2,3,那么2,3也是24的因子.....

semozhu

我不懂程序，不过厚着脸皮也来说下思路
这个自然数N肯定是有个最大范围，不然求最大质数也不会是一个世界大难题
1，然后要有个包含所有已知质数的质数表，然后取所有小于N/2的质数，每一个都试一次，选出所有为因子的质数,此为第一批约数集，par1
2，将N除以par1的每个质数，得到第二批约数集,par2
3，剔除Par2中的所有质数，然后将剩余的数去除以par1，得到所有约数
4，重复步骤3，直至得到的约数都为质数
5，将所有步骤的结果合并，再加上1和N本身