Efficiently calculating the 'prime-power sum' of a number.

Question

Let $n$ be a positive integer with prime factorization $p_1^{e_1}p_2^{e_2}\cdots p_m^{e_m}$. Is there an 'efficient' way to calculate the sum $e_1+e_2+\cdots +e_m$?

I could always run a brute force algorithm to factor $n$ and then calculate the sum directly, but that is unwieldy and roundabout. An easy upper bound is $\log_2(n)$, and we can successively improve it to $\log_p(n)$ for each $p$ that doesn't divide $n$. But I want the explicit sum instead of an upper bound.

I am unversed in number theory that is anything but elementary and was hoping someone here would have some insight in approaching this problem. Any help is appreciated.

I'm using the term 'efficient' loosely. If you can calculate the asymptotic runtime explicitly that's impressive and helpful (polynomial time would be great, if wishes do come true) but unnecessary.

Answer 1

I have a solution that runs in O(n*log(log(n))). Don't worry about factoring n; you can do that indirectly. Here's a crude draft of the algorithm:

1: Run a prime number sieve such as the Sieve of Eratosthenes to generate a list of all prime numbers less than or equal to n. This is the step that takes O(n*log(log(n))) time.

2: Create a total counter that will hold the value e₁+e₂+...+e_m and initialize it to zero.

3: Iterate through your list of primes. For each prime in your list, while that prime evenly divides n, divide n by that prime and increment your counter. When that prime no longer evenly divides n, move on to the next prime in your list. Repeat until n is reduced to one. Iterating through the entire list takes approximately O(n/ln(n)) time according to this, and the worst case for number of factors to divide by is log₂(n), giving this step a worst-case time complexity of O(n/ln(n)).

4: Your counter now holds the value of the sum e₁+e₂+...+e_m, and the program terminates. The running time is O(n*log(log(n))), which is definitely a polynomial time solution.

This is my first time posting an answer here; I hope it helps. Good luck!

Answer 2

As reply to @Roger's post I'm writing this answer. It's possible in $\mathcal{O}(\sqrt{n})$. In fact it will be just a little bit optimized brute-force algorithm.

We should notice, if we found $d$, such that $\left(\nexists d' \in \mathbb{Z}\right) \left( 2 \leq d' <d \wedge d' \mid n \right) \Rightarrow d \in \mathbb{P}$ ($\mathbb{P}$ - set of prime numbers). So we can find factorization of $n$ in $\mathcal{O}(\sqrt{n})$ time.

Why we can check just to $\sqrt{n}$? Because $\left(\nexists x,y\right)(x,y > \sqrt{n} \wedge xy \leq n)$, so $(\nexists x \in \mathbb{Z})(2 \leq x \leq \sqrt{n} \wedge x \mid n) \Rightarrow n \in \mathbb{P}$. It's obvious. So, below simple pseudo-code.

i = 2
count = 0
while i <= \sqrt{n} :
    while n \equiv 0 \mod{i} :
        n /= i
        ++count
    ++i
if n \neq 1 :
    count += 1

Always, when $n \equiv 0 \mod{i}$, $i$ has to be prime. Because all possible smaller primes are eliminated (therefore, we can use above fact).