J_factorize.py

"""
J. Факторизация

Основная теорема арифметики говорит: любое число раскладывается на
произведение простых множителей единственным образом, с точностью до их
перестановки. Например:

Число 8 можно представить как 2 × 2 × 2.
Число 50 –— как 2 × 5 × 5 (или 5 × 5 × 2, или 5 × 2 × 5). Три варианта
отличаются лишь порядком следования множителей.
Разложение числа на простые множители называется факторизацией числа.

Напишите программу, которая производит факторизацию переданного числа.

Формат ввода
В единственной строке дано число n (2 ≤ n ≤ 109), которое нужно факторизовать.

Формат вывода
Выведите в порядке не убывания простые множители, на которые раскладывается
число n.

Пример 1
Ввод
8
Вывод
2 2 2
"""

from math import sqrt
from typing import List

from ..timing import timing


@timing
def factorize(number: int) -> List[int]:
    j = 2
    while number > 1:
        for i in range(j, int(sqrt(number + 0.05)) + 1):
            if number % i == 0:
                number //= i
                j = i
                yield i
                break
        else:
            if number > 1:
                yield number
                break


if __name__ == "__main__":
    result = factorize(int(input()))
    print(" ".join(map(str, result)))