Prime Factorization Of A Number

Only prime number hi factor honge 

48 = 2 * 2*2*2 *3

240 = 2 * 2*2*2 *3 * 5

public class primeFactorization {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int num = sc.nextInt(); 

        int div = 2;

        while (num > 1) {
            if (num % div == 0) { // Check if 'div' is a factor of 'num'
                System.out.println(div);
                num = num / div; // Update 'num' after finding a factor
            } else if (div * div > num) { // Optimization: Stop if 'div' squared is greater than 'num'
                break;
            } else {
                div++; // Move to the next potential divisor if 'div' is not a factor
            }
        }

        if (num != 1) System.out.println(num); // Print the last remaining prime factor (if not 1)
    }
}

Time Complexity:

1. Best Case (O(1)): Consider a prime number like 17. The loop checks the divisibility by 2 (only one potential factor)
and exits since 17 is not divisible by 2. This results in a single loop iteration.

2. Worst Case (O(sqrt(n))): Imagine a highly composite number like 2520 (2^3 * 3 * 5 * 7). The loop needs to check 

potential divisors up to the square root (√2520 ≈ 50). This can lead to many iterations as it finds factors like 

2, 3, 5, 7, etc.

3. Average Case (O(sqrt(n))): Assuming randomly distributed input numbers, the average number of iterations will 

be somewhere between the best and worst cases, resulting in an average time complexity of O(sqrt(n)).

The time complexity of the primeFactorization algorithm is O(sqrt(n)) because it iterates through potential prime 
factors up to the square root of the input number n. This is due to the following property of prime factorization:
If a number n is not prime, it must have a prime factor less than or equal to its square root.
Number: 24
Factors:
1 * 24
2 * 12
3 * 8
4 * 6
Observations:
The prime factors of 24 are 2, 2, 2, and 3.
The square root of 24 is approximately 4.9.
All prime factors of 24 are less than or equal to 4.9.

Space Complexity:

The code uses a constant amount of additional space for variables (num and div) regardless of the input size (n). 

These variables hold integer values, and their space usage doesn't increase with the input size. Therefore, the space 

complexity remains O(1) in all cases.