[原创]自创了一个求n约数个数的O(logn)的算法

主题：[原创]自创了一个求n约数个数的O(logn)的算法

liji [专家分：530] 发布于 2006-01-07 22:06:00

算法思想的核心是乘法原理
但在最坏情况下(n为素数时)会退化到O(n^1/2)

沙发

iAkiak [专家分：8460] 发布于 2006-01-08 10:14:00

我最坏情况下是O(n)的...

for (t = 2, count = 1; n > 1; t++)
{
    for (d = 1; n > 1 && n % t == 0; d++)
        n /= t;
    count *= d;
}

请问如何达到O(logn)?

板凳

FancyMouse [专家分：13680] 发布于 2006-01-08 16:17:00

估计是算出来质因数分解式然后再乘起来的……

3 楼

iAkiak [专家分：8460] 发布于 2006-01-11 23:26:00

@FancyMouse, 2
那不是和我的一样？这复杂度是O(logn)嗯？

4 楼

euc [专家分：4310] 发布于 2006-01-31 22:39:00

1楼的方法是从小到大搜索。楼主提到乘法中的logn，那自然令人想起开平方，即是找离n^1/2最近的因数，然后递归分置……

您尚未登录，请登录后再回复。点此登录或注册