Problem

Given a positive integer n, write an efficient function to find all prime factors of n. The output should include each prime factor the number of times it divides n.

Examples

Example 1:

1
2
3
4

Input: 12
Output: [2, 2, 3]
Explanation:
 - 12 can be factorized into 2 * 2 * 3

Example 2:

1
2
3
4

Input: 16
Output: [2, 2, 2, 2]
Explanation:
 - 16 can be factorized into 2 * 2 * 2 * 2

Similar Problem

Find all unique combinations of factors for given number

Solution

Method 1 - Run the loop of sqrt n

Prime factorization involves breaking down a number into its prime factors. The approach involves:

  1. Checking and dividing the number by smallest primes starting from 2.
  2. Dividing continuously by the same prime number as long as it divides the current number.
  3. Moving to the next prime when the current prime no longer divides the number.

Approach

  1. Divide by 2: Continuously divide the number by 2 as long as it is even.
  2. Odd factors: Start from 3 and check odd numbers up to the square root of the number to check for factors. If a number divides the current number, it is a prime factor.
  3. Remaining number: If the remaining number after the above steps is greater than 2, it is a prime number.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

public class PrimeFactors {
    public List<Integer> primeFactors(int n) {
        List<Integer> factors = new ArrayList<>();

        // Check for number of 2s that divide n
        while (n % 2 == 0) {
            factors.add(2);
            n /= 2;
        }

        // Check for odd factors from 3 onwards
        for (int i = 3; i <= Math.sqrt(n); i += 2) {
            while (n % i == 0) {
                factors.add(i);
                n /= i;
            }
        }

        // If n is still a prime number greater than 2
        if (n > 2) {
            factors.add(n);
        }

        return factors;
    }

    public static void main(String[] args) {
        PrimeFactors solution = new PrimeFactors();
        System.out.println(solution.primeFactors(12));  // Output: [2, 2, 3]
        System.out.println(solution.primeFactors(16));  // Output: [2, 2, 2, 2]
        System.out.println(solution.primeFactors(15));  // Output: [3, 5]
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

class PrimeFactors:
    def prime_factors(self, n):
        factors = []
        
        # Check for number of 2s that divide n
        while n % 2 == 0:
            factors.append(2)
            n //= 2
        
        # Check for odd factors from 3 onwards
        for i in range(3, int(n**0.5) + 1, 2):
            while n % i == 0:
                factors.append(i)
                n //= i
        
        # If n is still a prime number greater than 2
        if n > 2:
            factors.append(n)
        
        return factors

# Example usage
pf = PrimeFactors()
print(pf.prime_factors(12))  # Output: [2, 2, 3]
print(pf.prime_factors(16))  # Output: [2, 2, 2, 2]
print(pf.prime_factors(15))  # Output: [3, 5]

Complexity

  • ⏰ Time complexity: O(n), where n is the number to be factorized. This is because we only need to check up to the square root of n.
  • 🧺 Space complexity: O(n), since the space required depends on the number of factors, which is limited by the number of times we divide n.