关于找到所有约数的算法

比如找 n 的所有约数
网上查到的都是从 1 到 n-1 迭代, 通过余数是否为 0 来判断, 效率无疑是很低的...
进一步想到, 其实从 1 迭代到(n/2)就可以了, 效率相对高了一点...
进一步又发现, 其实除了 1 之外的约数都是必定是成对出现的, 比如 80 的约数是 1, 2, 4, 5, 8, 10, 16, 20, 40, 想到可以从 2 开始迭代, 遇到能整除的情况, 就可以把整除后的结果作为迭代的终点, 这样范围可以迅速缩小, 找到 80 的所有约数只要迭代 8 次就可以了(2, 3, 4, 5, 6, 7, 8, 9)
因为搜不到啥资料...不知道是否还有更好的解法?

约数

迭

余数

n-1

14 条回复 • 2017-01-19 14:03:53 +08:00

66450146

2017-01-18 18:15:49 +08:00

不是 [2, sqrt(n)) 过一遍就好了么

luban

2017-01-18 18:27:39 +08:00

任意一个数都能表示成所有质数的乘积，根据这些质数可以算出有多少个约数
当然并不能确定表示成质数乘积的过程比单次遍历快
比如 80=2 的 4 次方*5 ，(4+1)*(1+1)=10
可参考这个
http://www.co8bit.com/index.php/2011/06/11/269/

billgreen1

2017-01-18 18:28:03 +08:00

@66450146 他要的是约数，不是质因子

htfy96

2017-01-18 18:49:12 +08:00

https://en.wikipedia.org/wiki/Integer_factorization#Current_state_of_the_art

jininij

2017-01-18 18:50:59 +08:00 via Android

先分解质因子，再合并出所有约数。如果你已经有了一个质数数组，那么分解这一步也可以做到很低的复杂度。

morefreeze

2017-01-18 19:07:27 +08:00

@billgreen1 那上界还是 sqrt(n)，没毛病啊
觉得大数情况下最快的办法还是找到所有质因子，然后组合出所有的约数吧，如 2L @luban 所说

owt5008137

2017-01-18 19:29:07 +08:00

到 sqrt(n)就可以了，算素数反正也是 O(n),不如直接过一遍完事儿

siriussilen

2017-01-18 20:17:20 +08:00

bool prime[maxv];
fill(prime,prime+maxv,true);
for(int i=0;i<maxv;++i) {
if(i%2==0) prime[i]=false;
}
for(int i=3;i<=sqrt(maxv);++i) {
if(prime[i]) {
for(int j=i*2;j<maxv;j+=i)
prime[j]=false;
}
}
求出 2-n 所有的素数时间复杂度 O(n)
楼主参考一下吧

siriussilen

2017-01-18 22:01:40 +08:00

@owt5008137 求模运算这个 O 可不低喔

owt5008137

2017-01-19 00:56:38 +08:00

@siriussilen 确实，取模消耗比较高。你这样好一些，就是麻烦点。

40huo

2017-01-19 09:44:20 +08:00

分解个 RSA 公钥这些算法都跪了。。。

wizardoz

2017-01-19 13:08:40 +08:00

@40huo 那你能给出一个不跪的分解 RSA 公钥的算法？

hanzichi

2017-01-19 13:49:09 +08:00

量大的话，我能想到的方法是先维护一个素数数组，然后分解质因子，然后深度优先搜索枚举约数 ...

40huo

2017-01-19 14:03:53 +08:00 via Android

@wizardoz 不能，但至少有比直接遍历好的，比如 yafu 用的算法。