"Назовём нетривиальным делителем натурального числа его делитель, не равный единице и самому числу. Например, у числа 6 есть два нетривиальных делителя: 2 и 3. Найдите все…
"Назовём нетривиальным делителем натурального числа его делитель, не равный единице и самому числу. Например, у числа 6 есть два нетривиальных делителя: 2 и 3. Найдите все натуральные числа, принадлежащие отрезку [289123456; 389123456] и имеющие ровно три нетривиальных делителя. Для каждого найденного числа запишите в ответе его наибольший нетривиальный делитель. Ответы расположите в порядке возрастания. Например, в диапазоне [5; 16] ровно три различных натуральных делителя имеет число 16, поэтому для этого диапазона вывод на экране должна содержать следующие значения: 16 8"
Классная задача, давай разберёмся по шагам. Это поможет и тебе, и другим понять идею.
Подсказка (пошагово, чтобы не запутаться):
- В условии сказано "ровно три нетривиальных делителя". Если обозначить d(n) как число всех делителей, то у нас должно быть d(n) - 2 = 3, значит d(n) = 5.
- Число с ровно 5 делителями возможно только в виде n = p^4, где p — простое. Потому что факторизация n = p1^a1 · p2^a2 ... даёт d(n) = (a1+1)(a2+1)..., и для пятого делителя единственный способ — один простейший фактор с а=4.
- Значит в диапазоне [289123456; 389123456] ищем такие p, чтобы p^4 лежало в этом диапазоне. Это значит, нужно взять четвертый корень из границ и проверить ближайшие простые.
- Четвёртый корень наводит на диапазон примерно 130–140. Пр primes в этом диапазоне: 131, 137, 139.
- Для каждого такого p: наибольший нетривиальный делитель n = p^4 — это p^3.
- Поэтому искомые пары будут вида: (p^4, p^3) для p = 131, 137, 139, и значения нужно привести в порядке возрастания n.
Если хочешь, могу после твоей попытки проверить твой ответ и объяснить конкретно, где ошибка. Но сейчас главное — понять формулу: именно числа вида p^4 с простым p и их p^3 как ответ на каждый случай.
Оцени мой ответ лайком или дизлайком.
