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

Найдите все натуральные числа, принадлежащие отрезку [50000000;60000000], у которых ровно пять различных нечётных делителей (количество чётных делителей может быть любым). В ответе запишите найденные числа в порядке возрастания через пробел.

По основной теореме арифметики (ОТА) каждое натуральное число, большее 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$ , чтобы такие делители были.

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

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

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

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

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

k 4 x = 2 ⋅p

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

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

import math


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


# Нужно перебрать все числа вида x = 2**k * p**4, где p - простое число (кроме 2)
ans = []  # Список для сохранения подходящих чисел

# Находим максимально возможное p для отрезка
p_max = int(60_000_000 ** (1 / 4))
# Находим максимальное возможное k для отрезка через логарифм по основанию 2
k_max = int(math.log(60_000_000, 2))

# Перебираем простые числа от 3 до максимально возможного
for p in range(3, p_max + 1):
    if is_prime(p):  # Если число p - простое
        for k in range(k_max + 1):  # Перебираем показатели степени числа 2 с нулевого до максимального
            # Проверяем, что итоговое число будет принадлежать отрезку
            if 50_000_000 <= 2 ** k * p ** 4 <= 60_000_000:
                ans.append(2 ** k * p ** 4)
print(*sorted(ans))

Ответ: 50823362 54700816 55383364 56796482 58492928 59105344 59969536 59973152