P2043 Prime Factorization of $N!$

Perform the prime factorization of $N!$.

The input consists of a single line containing a positive integer $N$, with $N \leq 10000$.

Output multiple lines. Each line contains two positive integers $p$ and $a$, separated by a single space, indicating that $N!$ contains $a$ copies of the prime factor $p$. Output them in increasing order of $p$.

$10! = 3628800 = (2^8) \times (3^4) \times (5^2) \times 7$. Translated by ChatGPT 5