Sum the exponents of the prime factors of a number

Question

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<Integer> candidatePrimeNumbers = findPrimesSmaller(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;
        }
      }
    }

    ArrayList<Integer> primeNumbers = new ArrayList<Integer>();
    for (int i = 2; i <= n; i++) { // Remove 0 and 1 from list => 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() {
    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();

  }
}

Answer 1

In addition to the other answer:

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.

Now about the code itself:

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

Answer 2

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