Prime Factorisation
mediumMath & Number Theory+20 XPTime limit 2s
Every number greater than 1 can be written as a product of primes in exactly one way, e.g. 360 = 2³ × 3² × 5. For each n, print its prime factorisation as prime^power pairs, primes in increasing order, separated by spaces. 360 is printed as 2^3 3^2 5^1.
There can be many queries, so make each one fast.
Input:
- line 1:
q - next
qlines: one integerneach
Output: q lines — the factorisation of each n.
Constraints: 1 ≤ q ≤ 10⁵, 2 ≤ n ≤ 10⁶.
Think about it: build a smallest prime factor table once with a sieve: spf[x] is the smallest prime dividing x. Then factorise any n by repeatedly dividing by spf[n] — that takes only about log₂ n steps per query.
Sample input 1
3 360 7 1000000
Sample output 1
2^3 3^2 5^1 7^1 2^6 5^6
Sample input 2
2 2 97
Sample output 2
2^1 97^1
Read input from standard input and print the answer to standard output. Your code runs in a secure sandbox against the samples (Run) and hidden tests (Submit).