# your code goes here
import math
from collections import defaultdict

MAXN = 1000000

# Array to store the smallest prime factor for each number
spf = [i for i in range(MAXN + 1)]

def compute_spf():
    """Precomputes the Smallest Prime Factor (SPF) for all numbers up to MAXN."""
    for i in range(2, int(math.isqrt(MAXN)) + 1):
        if spf[i] == i:  # i is prime
            for j in range(i * i, MAXN + 1, i):
                if spf[j] == j:  # Update spf[j] if not already updated
                    spf[j] = i

def get_prime_factors(num):
    """Returns a dictionary of prime factors and their powers for a given number."""
    factors = defaultdict(int)
    while num > 1:
        prime = spf[num]
        factors[prime] += 1
        num //= prime
    return factors

# --- Example Usage ---
compute_spf()

numbers_to_factor = [12, 100, 999999]

for num in numbers_to_factor:
    factors = get_prime_factors(num)
    formatted = " * ".join(
        [f"{p}^{count}" if count > 1 else str(p) for p, count in factors.items()]
    )
    print(f"{num} = {formatted}")