Как найти все делители данного числа? Можно ли упростить перебор, если вспомнить о парных делителях? Сколько делителей у чисел: а) 60; б) 136?

Коротко про метод. Чтобы найти все делители числа $n$:

1. Перебираем возможные делители $d$ от 1 до $\lfloor\sqrt n\rfloor$.

2. Если $d\mid n$, то одновременно получаем пару делителей: $d$ и $\frac{n}{d}$.

3. Если $d^2=n$, то $d$ засчитываем один раз (это «парный» к самому себе).

Такой «парный» перебор в разы сокращает работу: вместо всех чисел до $n$ проверяем только до $\sqrt n$, а второй делитель берём автоматически как пару.

Ещё быстрее — через разложение на простые множители: если

то число делителей равно $(\alpha_1+1)(\alpha_2+1)\cdots(\alpha_k+1)$.

Теперь к примерам.

а) $60$.
Разложение: $60=2^2\cdot3^1\cdot5^1$.
Число делителей: $(2+1)(1+1)(1+1)=3\cdot2\cdot2=12$.
Сами делители (по парам): $1,60;\;2,30;\;3,20;\;4,15;\;5,12;\;6,10$. Итого 12.

б) $136$.
Разложение: $136=2^3\cdot17^1$ (поскольку $136=8\cdot17$).
Число делителей: $(3+1)(1+1)=4\cdot2=8$.
Делители: $1,136;\;2,68;\;4,34;\;8,17$. Итого 8.

Итог: у 60 — 12 делителей, у 136 — 8 делителей. Перебор до $\sqrt n$ с учётом парных делителей — оптимальный способ их перечислить.