import time
import math

def prime_factorization(n):
    """Find prime factors of n using trial division - O(√n) complexity"""
    factors = []
    
    # Check for factor 2
    while n % 2 == 0:
        factors.append(2)
        n //= 2
    
    # Check odd factors up to √n
    i = 3
    while i <= math.isqrt(n):
        while n % i == 0:
            factors.append(i)
            n //= i
        i += 2
    
    # If n > 1, then n itself is prime
    if n > 1:
        factors.append(n)
    
    return factors


def demo_complexity(numbers):
    """Demo how time grows as numbers get larger"""
    print(f"{'Number':<25} {'Factors':<30} {'Time (ms)':<15} {'Divisions Checked'}")
    print("-" * 85)
    
    for n in numbers:
        start = time.perf_counter()
        
        # Count actual divisions checked (for complexity illustration)
        divisions = 0
        temp = n
        factors = []
        
        while temp % 2 == 0:
            factors.append(2)
            temp //= 2
            divisions += 1
        
        i = 3
        while i <= math.isqrt(temp):
            while temp % i == 0:
                factors.append(i)
                temp //= i
                divisions += 1
            i += 2
            divisions += 1  # Count the check itself
        
        if temp > 1:
            factors.append(temp)
        
        elapsed = (time.perf_counter() - start) * 1000
        
        factor_str = " × ".join(map(str, factors))
        print(f"{n:<25} {factor_str:<30} {elapsed:<15.4f} {divisions}")


# --- Demo ---
print("=" * 85)
print("PRIME FACTORIZATION - Classical Complexity Demo")
print("Algorithm: Trial Division  |  Complexity: O(√n)")
print("=" * 85)

# Small numbers - fast
small = [12, 100, 561, 9999]

# Medium numbers
medium = [1_000_003, 9_999_991, 99_999_989]

# Large semiprimes (product of two large primes) - hardest case!
# These expose worst-case complexity: no small factors, must check up to √n
large_semiprimes = [
    100_003 * 100_019,          # ~10^10
    999_983 * 999_979,          # ~10^12
    9_999_991 * 9_999_973,      # ~10^14
]

print("\n📌 Small Numbers:")
demo_complexity(small)

print("\n📌 Medium Numbers:")
demo_complexity(medium)

print("\n📌 Large Semiprimes (worst case - two large prime factors):")
demo_complexity(large_semiprimes)

print("\n" + "=" * 85)
print("KEY INSIGHT:")
print("  • Trial division checks up to √n candidates")
print("  • Doubling the digits of n → time grows EXPONENTIALLY")
print("  • Semiprimes (p × q) are worst case: no shortcuts available")
print("  • RSA encryption exploits this hardness with 2048-bit numbers!")
print("=" * 85)