目前我能做到的分解质因数是O(logn)，是否有更快的算法？

贴一道有关题：
题目描述：
丢番图是亚历山大时期埃及著名的数学家。他是最早研究整数系数不定方程的数学家之—。为了纪念他，这些方程一般被称作丢番图方程：
最著名的丢番图方程之一是xn+yn=zn ，费马提出，对于n>2，x,y,z没有正整数解。这被称为“费马大定理”，它的证明直到最近才被安德鲁•怀尔斯(Andrew Wiles)证明。
考虑如下的丢番图方程：
    1/x+1/y=1/z   (x,y,z属于N+)  (1)
    丢番图对下面这个问题十分感兴趣：对于一个给定的正整数z，有多少种本质不同解?满足方程(1)例如z=4，有三种本质不同解：
1/5+1/20=1/4
1/6+1/12=1/4
1/8+1/8=1/4
    显然，对于更大的z，很难去列举所有本质不同的解。你能否帮助丢番图快速求出对于给定z，满足方程(1)的本质不同的解的个数?
    输入
    一行，仅一个整数z(1≤z≤1014)。
    输出
    一行，输出对于给定整数z，满足方程(1)的本质不同的解的个数。
    样例输入
    4
    样例输出
    3
    对于30％的数据，z≤105
对于50％的数据，z≤231

啊错了，是O(sqrt(n))

回3L：
应该是没有了 可以先做个质数表优化一下(用const ...:array[...] of longint=(...)) 时间复杂度应该是没法再优了
回2L：
没看出和分解质因数有什么关系
就枚举x从z+1到2z 算下此时y的大小看是不是整数 复杂度是O(n)的
当然要用精确地分数计算：先通分

z最大是10^14 枚举要超时啊

我想的是，若m是z^2的因数，那么有
1/(z+m)+1/(z+z^2/m)=1/z
这就是一组本质不同解
那么就先分解z的质因数，进而获得z^2的质因数，从而通过排列组合求出z^2的因数个数，再 div 2，如果z是完全平方数再+1就是最后结果了

var c,n,i:longint;
begin
readln(n);
write(n,'=1');
i:=2;
while i<=n do
begin
while n mod i = 0 do
begin
write('*',i);
n:=n div i;
end;
inc(i);
end;
readln;
end.
分解质因数