Sum the exponents of the prime factors of a number

My goal is to find the sum of the exponents of the prime factors of an integer.

I wrote the code below with the complexities specified here (I am not 100% sure of the complexities though):

Runtime complexity:

-
findPrimesSmaller: \$O(n \log(\log n))\$

-
exponentInDecomposition: \$O(n)\$

-
primeExponentsCount: \$O(n^2 \log(\log n))\$

Space Complexity:

-
findPrimesSmaller: \$O(\log N)\$ (?)

-
exponentInDecomposition: \$O(1)\$

-
primeExponentsCount: \$O(\log N)\$

```
import static org.junit.Assert.*;

import java.util.*;

import org.junit.*;

public class PrimeCount {
// Given a number n and its associated prime numbers decomposition:
// n = p1 ^ (alpha1) p2 ^ (alpha2) ... * pn ^ (alphan)
// where all the pi's are prime numbers smaller than n
// return the sum of the alphai's

public int primeExponentsCount(int n) {
// First generate the list of prime numbers smaller than n
ArrayList candidatePrimeNumbers = findPrimesSmaller(n);

// initialize the sum
int result = 0;

for (int i : candidatePrimeNumbers) {
result += exponentInDecomposition(i, n);
}

return result;
}

public ArrayList findPrimesSmaller(int n) {

int[] allNumbers = new int[n + 1];

// Initialize the list with all the numbers smaller than n
for (int i = 0; i 0 && j % i == 0) {
allNumbers[j] = -1;
}
}
}

ArrayList primeNumbers = new ArrayList();
for (int i = 2; i start counting at 2
if (allNumbers[i] > 0) {
primeNumbers.add(i);
}
}

return primeNumbers;
}

public int exponentInDecomposition(int p, int n) {
int result = 0;

while (n % Math.pow(p, result) == 0 && n / Math.pow(p, result) >= 1) {
result++;
}
result--;

return result;
}

@Test
public void test_exponentZeroDecomposition() {
int a = exponentInDecomposition(3, 5);
assertEquals(0, a);
}

@Test
public void test_exponentNonZeroDecomposition() {

In addition to the other answer:

-
There is no need to generate all primes up to n. You can generate them up to sqrt(n). If something remains after the division by these primes, it is a prime.

-
There is no need to generate any prime numbers at all. This code does exactly what you need:

public int primeExponentsCount(int n) {
    if (n  1) {
        result++;
    }
    return result;
}

The time complexity of this algorithm is O(sqrt(n)). The space complexity is O(1). As you can see, there is much room for improvement for your initial solution in terms of efficiency.

Now about the code itself:

-
Writing self-evident comments is a bad practice. For instance, this comment doesn't serve any purpose.

// initialize the sum
int result = 0;

I would delete it.

-
Error handling. It looks like your primeExponentsCount does not expect to receive a negative number. Instead of returning a wrong result, I'd throw an exception:

public int primeExponentsCount(int n) {
    if (n < 0)
        throw new IllegalArgumentException("The number must be non-negative");
    ...
}

-
There are too many blank lines inside methods, in my opinion(it is conventional to separate methods from each other with an empty line, but it is not common to insert random blank lines inside a method's body).

StackExchange Code Review Q#82499, answer score: 10