Делители По данному натуральному числу выведите все его натуральные делители в порядке возрастания.

Входные данные

На вход подаётся единственное натуральное число n (n≤1000).

Выходные данные

Выведите все делители числа в порядке возрастания. Делители можно выводить на одной строке, разделяя пробелом, или на разных строках.

Для того чтобы найти все натуральные делители числа $n$, нужно использовать следующий подход:

1. Что такое делитель? Делитель числа $n$ — это такое число $d$, что $n$ делится на $d$ без остатка, то есть $n \mod d = 0$.

2. Как найти делители? Для числа $n$ все его делители — это такие числа, которые могут быть получены при делении $n$ на все числа от 1 до $n$, и остаток при этом должен быть равен нулю. То есть для каждого числа $d$ из диапазона от 1 до $n$ проверяется условие:

   $$n \mod d = 0$$

   Если условие выполняется, то $d$ — это делитель числа $n$.

3. Оптимизация поиска делителей Вместо того чтобы проверять все числа от 1 до $n$, можно проверять только до $\sqrt{n}$. Это связано с тем, что если $d$ — делитель числа $n$, то всегда существует такой делитель $\frac{n}{d}$, который также является делителем числа. Если мы находим $d$, то сразу можем записать и $\frac{n}{d}$ как второй делитель.

4. Порядок вывода делителей После того как все делители найдены, их нужно вывести в порядке возрастания. Для этого можно отсортировать найденные делители.

Пример: Рассмотрим число $n = 36$. Его делителями будут: 1, 2, 3, 4, 6, 9, 12, 18, 36.

Для поиска делителей можно использовать следующий алгоритм:

1. Пройти по всем числам от 1 до $\sqrt{n}$.
2. Для каждого числа $d$, если $n \mod d = 0$, добавить $d$ и $\frac{n}{d}$ в список делителей.
3. После нахождения всех делителей отсортировать их.

Реализация на Python:

python
import math
n = int(input())  # Считываем число n
divisors = set()  # Множество для хранения делителей, чтобы избежать дублирования
# Находим делители
for i in range(1, int(math.sqrt(n)) + 1):
    if n % i == 0:
        divisors.add(i)
        divisors.add(n // i)
# Выводим делители в порядке возрастания
print(" ".join(map(str, sorted(divisors))))

Пояснение:

1. Входное число $n$ считываем с помощью input().
2. Используем цикл от 1 до $\sqrt{n}$, проверяя делимость числа $n$ на текущий элемент $i$.
3. Если $i$ является делителем, добавляем в список и сам $i$, и $n//i$.
4. Для вывода делителей, сортируем их и выводим через пробел.

Пример 1: Вход:

36

Выход:

1 2 3 4 6 9 12 18 36

Пример 2: Вход:

28

Выход:

1 2 4 7 14 28

Таким образом, мы можем эффективно найти и вывести все делители числа $n$ в порядке возрастания.