Finding all prime factors

Question: Given a number, return all the prime factors and their corresponding number of occurrences.

Related Tags:

Understanding the problem

The question asks us to find every prime factor of a given input, along with its occurrences. So for example:

3
3 => 1
Since 31 = 3
6
2 => 1, 3 => 1
Since 21 x 31 = 6
28
2 => 2, 7 => 1
Since 22 x 71 = 28
200
2 => 3, 5 => 2
Since 23 x 52 = 200

Pseudocode

Let's go through the walking pseudocode for this problem.

  1. Initialize a HashMap object to store our prime factors and their corresponding number of occurrences.
  2. Start from the number (possiblePrimevalue) 2.
  3. If our input value is divisible by the current value, then place it into our HashMap. If already in the HashMap, increase its occurrence by one.
  4. Divide our input value by the possiblePrimevalue and repeat until all occurrence of possiblePrimevalue is counted for.
  5. Increment our possiblePrimevalue and repeat.

Note that we don't need to check for primes since we are picking our values starting at 2, and any possible composites will already have been divided out.

We also have a second while-loop that ensures that we keep looping until all occurrences of that prime value will be divided out. For example, if we had 28, we'd take out 2, then 2 again, and then 7.

import java.util.*;

public class FindPrimeFactors {

	public static void main(String[] args) {
		HashMap<Integer, Integer> factors = getPrimeFactors(Integer.parseInt(args[0]));

		for (Integer key : factors.keySet()) {
	        System.out.println("key, " + key + " value " + factors.get(key));
		}
	}

	public static HashMap<Integer, Integer> getPrimeFactors(int input) {

		HashMap<Integer, Integer> factors = new HashMap<>();

		int possiblePrimeFactor = 2;

		while (input != 1) {

			while (input % possiblePrimeFactor == 0) {

				if (factors.get(possiblePrimeFactor) == null) {
					factors.put(possiblePrimeFactor, 1);
				} else {
					factors.put(possiblePrimeFactor, factors.get(possiblePrimeFactor)+1);
				}

				input /= possiblePrimeFactor;

			}

			possiblePrimeFactor++;
		}

		return factors;

	}

}

Came up with a better solution or have a question? Comment below!