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

Найдите все натуральные числа, принадлежащие отрезку [ $33$ $333$ $333$ ; $99$ $999$ $999$ ], у которых ровно $7$ различных четных делителей. Общее количество делителей может быть любым. В ответе укажите количество данных чисел.

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

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

Пусть число имеет следующий вид:

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

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

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

Выпишем количество делителей числа, не содержащих степень числа 2, то есть не являющихся чётными:

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

Из общего количества делителей вычтем количество делителей, не являющихся чётными, и получим количество чётных делителей:

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

Обозначим произведение всех $qi$ за $m$ . Так как количество по условию должно быть равно 7, то $k⋅m = 7$ . Так как число 7 – простое, то либо $k = 7$ и $m = 1$ , либо $k = 1$ и $m = 7$ .

В первом случае это число $27$ , так как $m = 1$ означает, что других простых чисел в разложении числа нет.

Во втором случае произведение всех $qi$ равно 7, а значит только 1 множитель должен быть равен 7 (так как 7 – простое число). Отсюда некоторое $qi = 6$ . Поэтому число будет иметь вид $21 ⋅p6$ .

В общем случае это можно представить, как $6 2⋅p ,$ где $p$ – любое простое число (включая число 2, что обобщает эти два случая).

Таким образом, нужно будет перебрать простые числа так, чтобы получить все возможные числа вида $2 ⋅p6$ из отрезка $[33333333;99999999]$ .

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


ans = 0  # Счётчик для ответа

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

# Находим максимально возможное p для отрезка
p_max = int(99_999_999 ** (1 / 6))

# Перебираем простые числа от 2 до максимально возможного
for p in range(2, p_max + 1):
    if is_prime(p):  # Если число p - простое
        # То проверяем, что итоговое число будет принадлежать отрезку
        if 33_333_333 <= 2 * p ** 6 <= 99_999_999:
            ans += 1
print(ans)

Ответ: 2