I'm looking for an algorithm to find in how many ways it can be written a unit fraction as sum of two other units fractions . That is, given a natural number $k$, I need to find the number of sets $\{x,y\}$ such that $$\frac1{k}= \frac1{x}+\frac1{y}$$ Of course, this problem is equivalent to finding the number of $x$ between $k+1$ and $2k$ such that $x-k$ divides $kx$. And it is also equivalent to finding the number of $x$ between $1$ and $k$ that divide $k^2$. However, the only algorithm I know to solve this problems implies iterating and checking, and so takes time linear in $k$. I've been told there is a better way to solve this problem, but nothing comes to my mind. Could it be inferred a formula that gives this quantity in constant time? It doesn't seem so. If the answer is no, which is the most efficient algorithm you can think off that solves this problem?
EDIT: I found a way to do it in $\sqrt k$ time. It wasn't so difficult after all. However, I tested it in a web and the algorithm is still taking too much time comparing with other users'. So, your ideas are still welcome
The number of $x$ between $1$ and $k$ that divide $k^2$ is $\frac{n+1}2$, where $n$ is the number of divisors of $k^2$ (since except for $k$ the divisors of $k^2$ come in pairs $\left(x,k^2/x\right)$, each containing one divisor below $k$). The number of divisors of an integer with prime factorization $\prod_kp_k^{\alpha_k}$ is $\prod_k(\alpha_k+1)$. Thus your problem is solved if you know the prime factorization of $k$ (and thus of $k^2$). Conversely, you cannot do this faster than by finding the prime factorization, since knowing the number of factors of an integer tells you whether it’s prime, and all known algorithms for deciding whether an integer is prime work by factoring it (see Wikipedia).
Thus the most efficient (known) way to do this is to apply an efficient factorization algorithm to $k$ (see integer factorization).