소수 판별 및 소인수분해

def prime_factors(n: int) -> dict[int, int]:
    """Return prime factorization as {prime: exponent} dict."""
    if n < 2:
        return {}
    factors = {}
    d = 2
    while d * d <= n:
        while n % d == 0:
            factors[d] = factors.get(d, 0) + 1
            n //= d
        d += 1
    if n > 1:
        factors[n] = factors.get(n, 0) + 1
    return factors

def format_factorization(n: int) -> str:
    factors = prime_factors(n)
    parts = [f"{p}^{e}" if e > 1 else str(p) for p, e in sorted(factors.items())]
    return " × ".join(parts)

print(prime_factors(360))         # {2: 3, 3: 2, 5: 1}
print(format_factorization(360))  # 2^3 × 3^2 × 5
print(format_factorization(97))   # 97  (prime itself)