Problem B
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$:

  1. if $x$ is prime, print $x$ and stop

  2. factor $x$ into its prime factors $p_1, p_2, \ldots , p_ k$

  3. let $x = p_1 + p_2 + \cdots + p_ k$

  4. go back to step 1

Write a program that implements prime reduction.


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


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 1
3 1
5 1
23 2
5 5
5 6
CPU Time limit 3 seconds
Memory limit 1024 MB
Statistics Show
Greg Hamerly
Source Baylor Competitive Learning course
License Creative Commons License (cc by-sa)

Please log in to submit a solution to this problem

Log in