关于找到所有约数的算法

比如找 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 replies • 2017-01-19 14:03:53 +08:00

66450146

Jan 18, 2017

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

luban

Jan 18, 2017

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

billgreen1

Jan 18, 2017

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

htfy96

Jan 18, 2017

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

jininij

Jan 18, 2017 via Android

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

morefreeze

Jan 18, 2017

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

owt5008137

Jan 18, 2017

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

siriussilen

Jan 18, 2017

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

Jan 18, 2017

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

owt5008137

Jan 19, 2017

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

40huo

Jan 19, 2017

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

wizardoz

Jan 19, 2017

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

hanzichi

Jan 19, 2017

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

40huo

Jan 19, 2017 via Android

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