Description

This program reads a positive integer n and performs prime factorization.
For each prime factor, output the prime number followed by its exponent.
The prime factors must be listed in ascending order.

Hint:

• Start dividing n by the smallest prime (2).

• Count how many times it can be divided (that is the exponent).

• Continue with the next prime number (3, 5, 7, …) until n becomes 1.

 

Input

A single positive integer n.

Output

A sequence of integers, where each pair consists of a prime factor and its exponent, separated by a space.
Factors are listed from smallest to largest.

 

Take sample input 1 as example,

123456 = 2⁶ x 3¹x 643¹,

then, output

2 6 3 1 643 1 

Important Notes

• A newline (\n) is printed at the end of the output.

• A space must follow the last exponent before the newline.

• The formatting of the output must match the samples exactly.

For example, 

// Sample Output 1
2 6 3 1 643 1' ''\n'    // ' ' is a blank space, and '\n' is a newline character

 

Sample Input  Download

Sample Output  Download

Tags

Discuss