Prime Factorization in Java — Definition, Examples and Program

Prime Factorization in Java — Definition, Examples and Program

Prime Factorization means expressing a number as a product of its prime factors. A prime factor is a prime number that divides the given number exactly.

For example:

• 12 = 2 × 2 × 3
• 18 = 2 × 3 × 3
• 100 = 2 × 2 × 5 × 5

Prime factorization is widely used in cryptography, number theory, HCF/LCM problems, and optimization algorithms.

How Prime Factorization Works

Steps:

1. Start dividing the number by the smallest prime (2).
2. If divisible, keep dividing until it no longer divides.
3. Move to the next prime number (3, 5, 7...).
4. Stop when the number becomes 1.

Example 1

Number: 36

• 36 ÷ 2 = 18
• 18 ÷ 2 = 9
• 9 ÷ 3 = 3
• 3 ÷ 3 = 1

Prime Factorization: 2 × 2 × 3 × 3

Example 2

Number: 84

• 84 ÷ 2 = 42
• 42 ÷ 2 = 21
• 21 ÷ 3 = 7
• 7 ÷ 7 = 1

Prime Factors: 2 × 2 × 3 × 7

Java Program for Prime Factorization

import java.util.Scanner;

public class PrimeFactorization {

    public static void primeFactors(int num) {
        System.out.print("Prime Factors: ");

        // Print number of 2s.
        while (num % 2 == 0) {
            System.out.print(2 + " ");
            num /= 2;
        }

        // Check for odd factors from 3 onwards.
        for (int i = 3; i <= Math.sqrt(num); i += 2) {
            while (num % i == 0) {
                System.out.print(i + " ");
                num /= i;
            }
        }

        // Any number greater than 2 left is prime.
        if (num > 2) {
            System.out.print(num);
        }
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        System.out.print("Enter a number: ");
        int num = sc.nextInt();

        primeFactors(num);
    }
}

Sample Output

Enter a number: 60
Prime Factors: 2 2 3 5

Enter a number: 97
Prime Factors: 97

Practice Challenges

1. Modify the program to display factors in "a × b × c" format instead of space-separated numbers.
2. Write a program to find the prime factorization of all numbers from 1 to 100.
3. Modify the program to count how many times each prime factor appears (e.g., 36 → 2² × 3²).

Prime factorization is fundamental in mathematics and computer science. With this Java program, you can quickly break any number into its prime components.