Problem A
Prime Reduction
A prime number $p \geq 2$ is an integer which is evenly divisible by only two integers: 1 and $p$. A composite integer is one which is not prime. The fundamental theorem of arithmetic says that any integer $x$ can be expressed uniquely as a set of prime factors – those prime numbers which, when multiplied together, give $x$. Consider the prime factorization of the following numbers:
\[ 10 = 2 \times 5 \hspace{0.3in} 16 = 2 \times 2 \times 2 \times 2 \hspace{0.3in} 231 = 3 \times 7 \times 11 \]Consider the following process, which we’ll call prime reduction. Given an input $x$:
-
if $x$ is prime, print $x$ and stop
-
factor $x$ into its prime factors $p_1, p_2, \ldots , p_ k$
-
let $x = p_1 + p_2 + \cdots + p_ k$
-
go back to step 1
Write a program that implements prime reduction.
Input
Input consists of a sequence of up to $20\, 000$ integers, one per line, in the range $2$ to $10^9$. The number $4$ will not be included in the sequence (try it to see why it’s excluded). Input ends with a line containing only the number $4$.
Output
For each integer, print the value produced by prime reduction executed on that input, followed by the number of times the first line of the process executed.
Sample Input 1 | Sample Output 1 |
---|---|
2 3 5 76 100 2001 4 |
2 1 3 1 5 1 23 2 5 5 5 6 |