Prime Factorization with Exponents

Given a positive integer n, print its prime factorization. For each distinct prime factor, print the prime and the exponent to which it appears in n, ordered from smallest prime to largest. If n = 1, it has no prime factors at all.

Input: A single line containing one integer n. Output: First print an integer k - the number of distinct prime factors of n. Then print k lines, each containing two space-separated integers: a prime factor and its exponent in n's factorization, ordered from smallest prime to largest.

1 <= n <= 10^12

The special case n=1 (having NO prime factors at all) is worth checking explicitly - it's a valid input but produces an empty factorization, unlike every other positive integer.

Break a number down into its prime building blocks, showing how many times each prime appears. Brute force: Check every integer from 2 up to n directly for divisibility - this costs O(n), far too slow for n up to 10^12. Optimised: Trial division only needs to go up to sqrt(n) because once the remaining value's smallest possible prime factor would exceed its own square root, the remaining value must itself be a single prime - this bounds the total work by O(sqrt(n)) instead of O(n), with each found factor's exponent counted via repeated division.

1. Trial-divide n by every integer i starting from 2 up to sqrt(n): while i divides the CURRENT remaining value, keep dividing and count how many times. 2. Move to the next candidate divisor once i no longer divides the remaining value. 3. After the loop, if the remaining value is still greater than 1, that remainder is ITSELF a prime factor with exponent 1 (it has no factors left below its own square root to try).

Time: O(sqrt(n)) - trial division up to the square root of n. Space: O(log n), for storing the distinct prime factors found (bounded by how many distinct primes can multiply to at most n).

n=1 has zero prime factors, so k=0 and no further lines follow. n may itself be prime (e.g. 999999937), giving k=1 with exponent 1. n can be as large as 10^12, requiring trial division up to about 10^6.

Be ready to explain WHY the leftover remainder (if greater than 1 after the loop) must itself be prime - this is the key insight that avoids needing to trial-divide all the way up to n itself.