1. What Are Prime Factors?

Prime factors are the prime numbers that divide a given number exactly, without leaving a remainder. Every composite number can be expressed as a unique product of prime factors (Fundamental Theorem of Arithmetic).

2. How Trial Division Works

The trial division method systematically tests each integer starting from 2 to see if it divides the number:

Key Steps:

• Start with the smallest prime number (2)
• Check if it divides the current number
• If divisible, add to factors and divide the number
• Continue with the same prime until no longer divisible
• Move to the next integer

3. Algorithm Explanation

Time Complexity: O(√n) in the worst case when the number is prime. The algorithm only needs to check up to the square root of n because any factor larger than √n would have a corresponding factor smaller than √n.

Space Complexity: O(k) where k is the number of prime factors.

4. Using the Calculator

Instructions: Enter any integer greater than 1. The calculator will display the prime factorization. If the number is prime, it will be shown as a single factor with "(Prime Number)" indication.

5. Frequently Asked Questions (FAQ)

Q1: Why start from i=2?
A: 2 is the smallest prime number. Starting from 1 would be inefficient since every number is divisible by 1.

Q2: Why use while loop inside for loop?
A: The while loop ensures we extract all occurrences of the same prime factor before moving to the next number.

Q3: What is the maximum number this can handle?
A: Theoretically unlimited, but practically limited by PHP's integer size and execution time constraints.

Q4: Can this method handle very large numbers?
A: For very large numbers (hundreds of digits), more sophisticated algorithms like Pollard's Rho or Quadratic Sieve are more efficient.

Q5: Why does the algorithm work correctly?
A: By always starting from the smallest prime and completely dividing out each factor, we ensure that only prime factors are collected in the result.