Четный делитель имеет вид 2m, где m — целое число.
Если число n делится на 2m, то оно делится на 2 и на m.
Следовательно, число, имеющее четные делители, само должно быть четным.
Таким образом, мы можем исключить нечетные числа.
Какие четные делители есть у любого четного числа?
У четных чисел больше 2 есть как минимум два четных делителя: 2 и само это число.
Например, 10 делится на 2 и на 10.
Число n = 2m, где m простое, имеет ровно два четных делителя: 2 и 2m.
Этого недостаточно: нужен третий делитель.
Число n = 4m, где m > 2, имеет как минимум четыре четных делителя: 2, 4, 2m, 4m.
Перебор.
Давайте рассмотрим пример.
n = 30. Какие есть четные делители?
Мы знаем, что есть делители 2 и 30.
Чтобы лучше сориентироваться, можем разложить число на множители:
30 = 5 • 6 = 5 • 3 • 2
Число 30 образовано тремя разными простыми множителями, один из них четный.
Это значит, что число 30 делится как на каждый из этих множителей (2, 3, 5), так и на любую комбинацию этих множителей (2 • 3 = 6, 2 • 5 = 10, 3 • 5 = 15, 2 • 3 • 5 = 30).
Вы можете заметить, что двойка, комбинируясь с двумя нечетными множителями (3 и 5), дает два четных делителя — 6 и 10.
Всего выходит четыре делителя: 2, 6, 10, 30.
Это не вариант.
В общем случае, если n = 2 • a • b, где a и b — различные целые больше 1, мы всегда имеем как минимум четыре четных делителя: 2, 2a, 2b, 2ab.
Таким образом, мы можем исключить четные числа n, такие, что n/2 раскладывается на два разных множителя.
Но что, если a = b = x, где x — целое простое число?
Тогда n = 2 • x • x = 2x². Его делители: 2, 2x, 2x², x².
x² здесь лишний: квадрат нечетного тоже нечетный, исключаем его (нам нужны четные делители; x = 2 не рассматриваем, но там тоже будут три делителя).
Остаются три делителя: 2, 2x, 2x².
Таким образом, можно уверенно сказать, что число n имеет ровно три различных четных делителя, если его половина равна квадрату простого числа.
Остается найти такие простые числа x, для которых 2x² принадлежит указанному вами интервалу. Эти 2x² и будут искомыми числами.
Возникает вопрос: в каком интервале следует проверять иксы на простоту?
Возьмем на заметку:
Ѵ(101 000 000 / 2) ≈ 7106,335
2 • 7106² = 100 990 472 (ниже интервала)
2 • 7107² = 101 018 898 (годится)
Ѵ(102 000 000 / 2) ≈ 7141,428
2 • 7141² = 101 987 762 (годится)
2 • 7142² = 102 016 328 (выше интервала)
Таким образом, нужно рассмотреть иксы от 7107 до 7141.
Для простых иксов рассчитаем 2x², это и будут числа с тремя четными делителями.
даю две подсказки:
1) наивный алгоритм разложения на простые множители (ну или нахождения всех делителей, одно и то же в принципе) работает за O(sqrt(n)), а не за O(n), как ты написал
перебирать потенциальные делители можно до корня от i, а не от i/2, тогда программа заработает гораздо быстрее
2) попробуй повыводить не сами числа, а их разложения на простые множители
там достаточно простая закономерность, всего две "формы" разложения подходят под условие, и одна из них содержит всего одно число, не входящее в диапазон поиска
нет, даже три:
3) итоговое решение, скорее всего, подразумевает использование решета эратосфена, вместо того, чтобы перебирать все числа в промежутке и проверять, удовлетворяют ли они условию, ты будешь перебирать все числа, удовлетворяющие условию, и проверять, входят ли они в промежуток
