Найдите все числа от 1000 до 2000, у которых ровно три различных делителя

Решение по шагам

1. 1

   Шаг 1. Почему у «обычного» числа делителей чётное количество

   Делители любого натурального $n$ естественно разбиваются на пары: если $d$ — делитель, то и $n/d$ — тоже делитель, и они «смотрят» друг на друга. Например, для $n = 12$: пары $(1;12)$, $(2;6)$, $(3;4)$ — всего 6 делителей.

   Пара «схлопывается» в один элемент только тогда, когда $d = n/d$, то есть $d^2 = n$.

   Отсюда ключевой вывод: количество делителей нечётно тогда и только тогда, когда $n$ — полный квадрат. Нам нужно ровно 3 делителя, число нечётное, значит искать надо только среди полных квадратов.

2. 2

   Шаг 2. Какие полные квадраты дают ровно три делителя

   Пусть $n = m^2$. Тогда среди делителей заведомо есть $1$, $m$ и $m^2$ — уже три штуки (и они попарно различны при $m > 1$).

   Чтобы других делителей не появилось, у самого $m$ не должно быть собственных делителей, кроме 1 и $m$: любой делитель $q$ числа $m$, отличный от 1 и $m$, добавил бы к списку делителей $n$ и сам $q$, и число $qm$.

   Значит, $m$ обязано быть простым, и искомые числа — это в точности квадраты простых чисел:

   $$n = p^2, \qquad p \text{ — простое}.$$

   Остаётся понять, какие простые $p$ дают квадрат внутри отрезка.