Problem D
Fundamental Neighbors
The fundamental theorem of arithmetic says that any natural number greater than one can be written uniquely as the product of prime numbers. For example: $3 = 3^1$, $4 = 2^2$, $6 = 2^1 \times 3^1$, $72 = 2^3 \times 3^2$, and in general,
\[ n = p_1^{e_1}\times p_2^{e_2}\times \cdots \times p_ k^{e_ k} \]for prime numbers $p_1$ through $p_ k$ and exponents $e_1$ through $e_ k$.
For this problem, given an integer $n \geq 2$, determine what we will call the ‘neighbor’ of $n$. The neighbor is the integer you get by swapping the $p_ i$ and $e_ i$ values in the prime factorization of $n$. That is, if $n$ is written in prime factorization as above, the neighbor of $n$ is
\[ e_1^{p_1}\times e_2^{p_2}\times \cdots \times e_ k^{p_ k}. \]For example, if $n = 2\, 000 = 2^4\times 5^3$ then its neighbor is $4^2\times 3^5=3\, 888$.
Input
Input is a sequence of up to $20\, 000$ integers, one per line. Each integer is in the range $2 \le n < 2^{31}$. Input ends at the end of file.
Output
For each $n$, print $n$ followed by its neighbor. Each neighbor is in the range $[1,2^{31})$.
| Sample Input 1 | Sample Output 1 |
|---|---|
2 3 4 5 6 7 8 9 10 72 200 |
2 1 3 1 4 4 5 1 6 1 7 1 8 9 9 8 10 1 72 72 200 288 |
