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

Найдите все натуральные числа, принадлежащие отрезку [20 000 000;25 000 000], у которых ровно пять различных нечётных делителей. Общее количество делителей может быть любым. В ответе перечислите найденные числа через пробел в порядке возрастания.

По основной теореме арифметики (ОТА) каждое натуральное число, большее 1, можно разложить на простые множители. То есть некоторое натуральное число $x$ можно разложить в следующий вид:

x = p1q1 ⋅p2q2 ⋅...⋅pnqn

Здесь $pi,i ∈ [1;n]$ – некоторое простое число, а $qi,i ∈ [1;n]$ – натуральный показатель степени. В таком случае число обязательно имеет $(q1 + 1)⋅(q2 + 1)⋅...⋅(qn + 1)$ делителей (каждое простое число можно брать от 0 до $qi$ раз, где $i ∈ [1;n]$ ).

В данной задаче необходимо, чтобы у числа было ровно 5 нечётных делителей. Значит, число должно содержать в разложении некоторое простое нечётное число.

Пусть число имеет следующий вид (отдельно выпишем простое число 2 в разложении):

x = 2k ⋅p1q1 ⋅...⋅pnqn

Выпишем количество нечётных делителей числа:

(q1 + 1)⋅(q2 + 1)⋅...⋅(qn + 1)

Это количество должно быть равно 5 – простому числу, а значит в этом произведении только 1 множитель, равный числу 5. Поэтому число должно иметь следующий вид:

k 4 x = 2 ⋅p

Здесь показатель степени k может быть любым неотрицательным числом, так как степень числа 2 не влияет на количество нечётных делителей.

Таким образом, нужно будет перебрать простые числа p (исключая 2) так, чтобы получить все возможные числа вида $k 4 2 ⋅p$ из отрезка $[20000000;25000000]$ .

def is_prime(n):  # Функция проверки, является ли число простым
    if n == 1:  # Единицу нужно проверить отдельно
        return False  # 1 - не простое число, возвращаем False
    for i in range(2, int(n ** 0.5) + 1):
        if n % i == 0:  # Если нашли нетривиальный делитель
            return False  # То число не простое, возвращаем False
    return True


# Нужно перебрать все числа вида x = 2**k * p**4, где p - простое число

r = 25_000_000  # Левая граница отрезка
r = int(r ** (1 / 4))  # Извлечём корень 4 степени, чтобы получить максимальное возможное p

# Перебираем числа от l до r включительно
ans = []  # Список чисел для ответа
for p in range(3, r + 1):  # Перебираем возможные простые числа
    if is_prime(p):  # Если число p - простое
        # Пока число не выйдет за верхнюю границу отрезка,
        # будем проверять его и увеличивать степень числа 2
        num = p ** 4
        while num <= 25_000_000:
            if 20_000_000 <= num <= 25_000_000:
                ans.append(num)
            num *= 2  # Увеличиваем степень числа 2

print(*sorted(ans))  # Выводим элементы сортированного списка через пробел

Ответ: 20151121 20480000 21233664 21381376 22606088 22632992 24234722