Факторизация

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

Например, число 8 можно представить как 2 × 2 × 2.

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

Разложение числа на простые множители называется факторизацией числа.

Факторизацию в уме делать сложно, поэтому помогите Тимофею написать для этого программу.

Формат ввода

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

Формат вывода

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

chislo = int(input())
d = 2
while d * d <= chislo:
    if chislo % d == 0:
        print(d, end=' ')
        chislo //= d
    else:
        d += 1
if chislo > 1:
    print(chislo)


Вы можете оставить комментарий, или Трекбэк с вашего сайта.

Оставить комментарий