# 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

// initialize the sum
int result = 0;

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

return result;
}

public ArrayList<Integer> findPrimesSmaller(int n) {

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

// Initialize the list with all the numbers smaller than n
for (int i = 0; i <= n; i++) {
allNumbers[i] = i;
}

// Apply a Sieves of Eratosthenes method to keep only the prime numbers
for (int i = 2; i <= n; i++) {
for (int j = i + 1; j <= n; j++) {
if (j > 0 && j % i == 0) {
allNumbers[j] = -1;
}
}
}

for (int i = 2; i <= n; i++) { // Remove 0 and 1 from list => start counting at 2
if (allNumbers[i] > 0) {
}
}

}

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() {
int a = exponentInDecomposition(3, 9);
assertEquals(2, a);
}

@Test
public void primesSmaller10() {
ArrayList<Integer> primesLessThan10 = findPrimesSmaller(10);
int two = primesLessThan10.get(0);
int three = primesLessThan10.get(1);
int five = primesLessThan10.get(2);
int seven = primesLessThan10.get(3);
assertEquals(2, two);
assertEquals(3, three);
assertEquals(5, five);
assertEquals(7, seven);
}

@Test
public void testCount0() {
int zero = primeExponentsCount(0);
assertEquals(0, zero);
}

@Test
public void testCount1() {
int zero = primeExponentsCount(1);
assertEquals(0, zero);
}

@Test
public void testCount10() {
int two = primeExponentsCount(10);
assertEquals(2, two);
}

@Test
public void testCount13() {
int one = primeExponentsCount(13);
assertEquals(1, one);
}

public static void main(String[] args) {
PrimeCount e = new PrimeCount();
e.test_exponentZeroDecomposition();
e.test_exponentNonZeroDecomposition();
e.primesSmaller10();
e.testCount0();
e.testCount1();
e.testCount10();
e.testCount13();

}
}


1. 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.

2. 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)
return 0;
int sqrt = (int) Math.sqrt(n);
int remainingNumber = n;
int result = 0;
for (int i = 2; i <= sqrt; i++) {
while (remainingNumber % i == 0) {
result++;
remainingNumber /= i;
}
}
if (remainingNumber > 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.

1. 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.

2. 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");
...
}

3. 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).

• Note too that i * i <= remainingNumber may be faster than recalculating the root. Also I disagree about blank lines; spacing is good and should be encouraged. Commented Feb 25, 2015 at 5:35
• You should change the termination condition to for (int i = 2; i <= sqrt && i <= remainingNumber; i++). Commented Feb 25, 2015 at 6:31
• @200_success It is an optimization, but, again, the code is correct without it. If i > remainingNumber, remainingNumber is never divisible by i so nothing happens. Commented Feb 25, 2015 at 6:34
• exponentInDecomposition is suboptimal.

while (n % p == 0) {
result += 1;
n /= p;
}


has the same amount of modulos and divisions, and not a single call to Math.pow.

• Eratosthenes Sieve is suboptimal.

for (int i = 2; i <= n; i++)


means that you try to eliminate numbers using composite i. Waste of time - numbers are actually eliminated with i being a (known) prime. Testing i greater than $\sqrt{n}$ is also unnecessary.

for (int j = i + 1; j <= n; j++)


also wastes time: you may safely start with i*i, and increment i by 2 (all even numbers has already been eliminated).