Задача к ЕГЭ по информатике на тему «делители числа» №14

Просмотров 5 Комментарии 0

Определите количество составных натуральных чисел из диапазона $[3;30000]$ , у которых количество нетривиальных делителей не менее трех.

Примечание. Нетривиальный делитель — делитель, не равный единице и самому числу.

ans = 0
for i in range(3, 30000 + 1):
    dels = 0
    for j in range(2, int(i ** 0.5) + 1): # перебор возможных нетривиальных делителей
        if i % j == 0:
            dels += 1
            if j != i // j:
                dels += 1
    if dels >= 3:
        ans += 1
print(ans)

Ответ: 19282