Тимофей готовит доклад ко дню открытых дверей кафедры Теории чисел. Он собирается рассказать про Основную теорему арифметики. В соответствии с этой теоремой, любое число раскладывается на произведение простых множителей единственным образом –— с точностью до их перестановки.
Например, число 8 можно представить как 2 × 2 × 2.
Число 50 –— как 2 × 5 × 5 (или 5 × 5 × 2, или 5 × 2 × 5). Три варианта отличаются лишь порядком следования множителей.
Разложение числа на простые множители называется факторизацией числа.
Факторизацию в уме делать сложно, поэтому помогите Тимофею написать для этого программу.
В единственной строке дано число n (2 ≤ n ≤ 109), которое нужно факторизовать.
Выведите в порядке неубывания простые множители, на которые раскладывается число n.
| Ввод | Вывод |
|---|---|
| 8 | 2 2 2 |
| Ввод | Вывод |
|---|---|
| 13 | 13 |
| Ввод | Вывод |
|---|---|
| 100 | 2 2 5 5 |