# Arup Guha
# 6/20/2026
# Commented version of code used for COT 3100 Exam #2 (Summer 2026)

# Prints out the prime factorization of n!
def whatdoesitdo(n):

    # Use for prime sieve.
    a = [True]*(n+1)

    # Outer prime sieve loop.
    for i in range(2, n+1):

        # If this is true, then i is a prime number.
        if a[i]:

            # Run the inner prime sieve loop, marking composites.
            for j in range(2*i, n+1, i):
                a[j] = False

            # Here we figure out how many times i divides evenly into n!
            x = 0
            y = n

            # We do repeated integer division until this quantity goes to 0.
            while y > 0:

                # Number of "cross-offs" on this pass.
                x += y//i

                # New values created after cross offs for next iteration.
                y = y//i

            # This is the number of times i divides evenly into n!
            print("(",i,"^",x,") *", sep="", end=" ")

    print()

# Quick test.
whatdoesitdo(100)