Description

[[Category: Prime]] 

Webster defines prime as:

 

prime (prim) n.[ME, fr. MF, fem. of prin first, L primus; akin to L prior] 

1 :first in time: original

2 a : having no factor except itself and one 3 is a   number  b : having no common factor except one  12 and 25 are relatively  

3 a : first in rank, authority or significance : principal b : having the highest quality or value   television time  [from Webster's New Collegiate Dictionary]

 

The most relevant definition for this problem is 2a: An integer g>1 is said to be prime if and only if its only positive divisors are itself and one (otherwise it is said to be composite). For example, the number 21 is composite; the number 23 is prime. Note that the decompositon of a positive number g into its prime factors, i.e., 

 

 

is unique if we assert that f_i > 1 for all i and  for i<j.

One interesting class of prime numbers are the so-called Mersenne primes which are of the form 2^p- 1. Euler proved that 2³¹ - 1 is prime in 1772 -- all without the aid of a computer.

Input

 The input will consist of a sequence of numbers (at most 800 numbers). Each line of input will contain one number g in the range -2³¹ < g <2³¹, but different of -1 and 1. The end of input will be indicated by an input line having a value of zero.

Output

 For each line of input, your program should print a line of output consisting of the input number and its prime factors. For an input number , where each f_i is a prime number greater than unity (with  for i<j), the format of the output line should be

 

 

When g < 0, if , the format of the output line should be 

 

Sample Input  Download

Sample Output  Download

Tags

Add Tag

Discuss