Напишите программу на Python, которая находит количество натуральных делителей числа $n$. Затем — для всех чисел от 100000 до 100100 найдите те, у которых ровно 6 делителей.
Перебор до √n
Делители идут парами: если $d$ делит $n$, то $n/d$ тоже. Поэтому проверяем только до $\sqrt{n}$, а парный делитель добавляем сразу.
def count_divisors(n: int) -> int:
count = 0
i = 1
while i * i <= n:
if n % i == 0:
count += 1
if i != n // i:
count += 1
i += 1
return count
print(count_divisors(12)) # 6 (1,2,3,4,6,12)
print(count_divisors(36)) # 9
Важный нюанс: для полного квадрата ($n = k^2$) пара $(k, k)$ — это один и тот же делитель, поэтому if i != n // i.
Цикл для интервала:
result = []
for n in range(100000, 100101):
if count_divisors(n) == 6:
result.append(n)
print(result)
Сложность $O(\sqrt{n})$ на одно число — для $n=10^9$ это ~31623 шага, мгновенно.
Кстати, ровно 6 делителей имеют числа вида $p^5$ или $p^2 q$, где $p,q$ — разные простые. Например, $12 = 2^2 \cdot 3$.
Razbery — про разбор, не про списывание. Объяснение обязательно.