Prime Factorization

/*
 * Problem : Write a number as a product of prime numbers.
 * Input   : One integer n, n >= 2.
 * Output  : The prime factors in ascending order, separated by a space.
 * Approach: Divide by the smallest possible divisor again and again.
 * Time    : O(sqrt(n))
 * Space   : O(1)
 * Java    : 8 or newer.
 */
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        long number = new Scanner(System.in).nextLong();
        StringBuilder result = new StringBuilder();

        // Step 1: Start with the smallest prime number, which is 2.
        long divisor = 2;

        // Step 2: Stop when divisor * divisor is larger than the rest of the number.
        while (divisor * divisor <= number) {
            // Step 3: While the divisor divides the number, it is a prime factor. Write it and divide the number.
            while (number % divisor == 0) {
                if (result.length() > 0) {
                    result.append(" ");
                }
                result.append(divisor);
                number = number / divisor;
            }

            // Step 4: Try the next number. Composite divisors never divide, because their prime parts were removed before.
            divisor++;
        }

        // Step 5: If something larger than 1 is left, it is a prime number and it is the last factor.
        if (number > 1) {
            if (result.length() > 0) {
                result.append(" ");
            }
            result.append(number);
        }

        // Step 6: Print the prime factors.
        System.out.println(result);
    }
}