import time
import math

def prime_factorization_timed(n):
    """Trial division with live progress updates"""
    factors = []
    divisions = 0
    temp = n

    while temp % 2 == 0:
        factors.append(2)
        temp //= 2
        divisions += 1

    i = 3
    sqrt_n = math.isqrt(temp)
    last_print = time.time()

    while i <= math.isqrt(temp):
        while temp % i == 0:
            factors.append(i)
            temp //= i
            divisions += 1
            sqrt_n = math.isqrt(temp)

        # Live progress every 3 seconds
        if time.time() - last_print >= 3:
            progress = (i / sqrt_n) * 100
            print(f"  ⏳ Still working... checked up to {i:,}  |  √n = {sqrt_n:,}  |  Progress: {progress:.2f}%")
            last_print = time.time()

        i += 2
        divisions += 1

    if temp > 1:
        factors.append(temp)

    return factors, divisions


def demo(label, n):
    print(f"\n{'='*70}")
    print(f"  {label}")
    print(f"  Number : {n:,}")
    print(f"  Digits : {len(str(n))}")
    print(f"{'='*70}")

    start = time.perf_counter()
    factors, divisions = prime_factorization_timed(n)
    elapsed = time.perf_counter() - start

    factor_str = " × ".join(map(str, factors))
    print(f"\n  ✅ Done!")
    print(f"  Factors    : {factor_str}")
    print(f"  Divisions  : {divisions:,}")
    print(f"  Time taken : {elapsed:.2f} seconds")


# ---------------------------------------------------------------
# These are semiprimes: n = p × q (two large primes)
# Worst case for trial division — no small factors, must grind to √n
# ---------------------------------------------------------------

# ~30 seconds
n1 = 2_999_999_999_999 * 3_000_000_000_037

# ~1 minute
n2 = 9_999_999_999_971 * 9_999_999_999_973

# ~2 minutes
n3 = 31_622_776_601_683 * 31_622_776_601_719

print("=" * 70)
print("  PRIME FACTORIZATION — Large Semiprime Stress Test")
print("  Algorithm : Trial Division  |  Complexity: O(√n)")
print("  These numbers have NO small factors — maximum work required!")
print("=" * 70)

demo("LEVEL 1 — ~30 seconds", n1)
demo("LEVEL 2 — ~1 minute",   n2)
demo("LEVEL 3 — ~2 minutes",  n3)

print(f"\n{'='*70}")
print("  💡 TAKEAWAY:")
print("  Each level only adds ~1-2 digits to the primes,")
print("  but the time DOUBLES or more — this is exponential growth.")
print("  RSA uses primes with 300+ digits. Classically: IMPOSSIBLE.")
print(f"{'='*70}\n")