Prime factorization involves expressing a composite number as a product of prime numbers. A prime number is a natural number greater than 1 that has no positive divisors other than 1 and itself.

Factorizaiton Algorithm

The algorithm proceeds as follows:

1. Initialize with the smallest prime number (2)
2. Divide the target number repeatedly by the current prime factor
3. When division is no longer possible, increment to the next prime
4. Continue until the quotient becomes 1

import java.util.Scanner;

public class PrimeFactors {
    public static void main(String[] args) {
        Scanner input = new Scanner(System.in);
        System.out.print("Enter a positive integer: ");
        int number = input.nextInt();
        
        System.out.print("Prime factors: ");
        factorize(number);
        input.close();
    }

    public static void factorize(int n) {
        if (n < 2) {
            System.out.println("Number must be greater than 1");
            return;
        }
        
        for (int factor = 2; factor <= n; factor++) {
            while (n % factor == 0) {
                System.out.print(factor);
                n /= factor;
                if (n > 1) System.out.print(" * ");
            }
        }
        System.out.println();
    }
}

Example Execution

For input value 36, the factorization process yields:

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

Final result: 2 * 2 * 3 * 3