Skills101
← All coding problems

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 q lines: one integer n each

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).

Loading editor…

Log in to run and submit your code — it's free.