Prime factorization (Java, HashSet, ArrayList, Set, List)

This is an article about the “prime factorization” problem.

As I solve coding test problems, I look back on the problems I solved and look into different solution methods to learn more.

Let’s look at the problem first.

problem

Prime factorization is expressing a number as a product of prime numbers.

For example, the prime factorization of 12 can be expressed as 2 _ 2 _ 3.

So the prime factors of 12 are 2 and 3.

When a natural number n is given as a parameter, complete the solution function so that it returns an array containing the prime factors of n in ascending order.

Restrictions

• 2 ≤ n ≤ 10,000

Input/Output Example

My solution to the problem

import java.util.*;

class Solution {
     public int[] solution(int n) {
         List<Integer> factors = new ArrayList<>();

         for (int i = 2; i <= n; i++) {
             while (n % i == 0) {
                 factors.add(i);
                 n /= i;
             }
         }

         Set<Integer> set = new HashSet<>();

         List<Integer> result = new ArrayList<>();

         for (int element : factors) {
             if (set.add(element)) {
                 result.add(element);
             }
         }

         int[] answer = new int[result.size()];
         for (int i = 0; i < result.size(); i++) {
             answer[i] = result.get(i);
         }

         return answer;
     }
}

Solution explanation

• List factors: A list that stores prime factors. Find the prime factors that can divide the given number n, starting from 2, and add them to the list.
• Set set: HashSet to exclude duplicate prime factors. Used to prevent duplication.
• List result: List to save excluding duplicate prime factors.
• Prime factorization: Find the prime factors that can divide the given number n starting from 2 through the for statement, add the corresponding prime factors to the factors list, and update n.
• Excluding duplicate prime factors: Use set to exclude duplicate prime factors and add unique prime factors to the result list.
• Conversion to array: Converts the result list to an array and returns it as the final result, an answer.

Code Advantages

• Using HashSet: You can simply remove duplicates by using HashSet to exclude duplicate prime factors.
• List utilization: List was effectively used to find prime factors and save the results excluding duplicate prime factors.

Code Disadvantages

• List conversion: The process of converting a List to an int[] array may seem complicated, but starting with Java 8, it can be expressed more simply using lambda expressions and stream APIs.