Problem statement

Given an integer, $N$, print all the prime factors of $N$.

Input format

A single line of input contains an integer $N$ $(1 \leq N \leq 10^{10})$.

Output format

Print all the prime factors of $N$.

---

Sample

Input 1: `

24

Output 1:

2 3

Input 2:

207

Output 2:

3 23

---

Explanation

$24 = 2^{3} \times 3$, prime factors are $2$ and $3$

$207 = 3^{2}\times23$, prime factors are $3$ and $23$

---

Solution

Starting from $i=2$ and going up to $\sqrt{N}$; if $i$ divides $N$, add this to the list of prime factors and remove all occurrences of $i$ by repetitively dividing $N$ by $i$.

In the end, if the number is completely factored, we are left with $1$, in which case we are done.

If we do not end up with $1$, that means $N$ has a prime factor $> \sqrt{N}$. This prime factor is the number we are left with since it’s power will be $1$ (as discussed earlier).