Prime factorization

Interview

Time limit1sMemory limit256 MB

Summary

Print the prime factors of N up to 10,000,000 in ascending order, repeating each factor by multiplicity.

Level: Easy3 of 10
Topics: Number theory
Solved: No attempts yet

Problem

Given an integer $N$ , write a program that factors $N$ into primes.

Input

The first line contains an integer $N$ ( $1 \le N \le 10\,000\,000$ ).

Output

Print the prime factors of $N$ in ascending order, one per line. If a prime divides $N$ several times, print it once for each division. If $N$ is $1$ , print nothing.

Examples5

Example 1
Input
```
72
```
Expected output
```
2
2
2
3
3
```
Example 2
Input
```
3
```
Expected output
```
3
```
Example 3
Input
```
6
```
Expected output
```
2
3
```
Example 4
Input
```
2
```
Expected output
```
2
```
Example 5
Input
```
9991
```
Expected output
```
97
103
```