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

Напишите программу, которая ищет среди целых чисел, принадлежащих числовому отрезку $[1732864;7146924]$ числа, у которых ровно $7$ делителей, сумма цифр которых некратна $3$ . Общее количество делителей может быть любым. Программа должна вывести количество таких чисел.

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

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

k q1 qn x = 3 ⋅p1 ⋅...⋅pn

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

(q + 1)⋅(q + 1)⋅...⋅(q + 1) 1 2 n

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

k 6 x = 3 ⋅p

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

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

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


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

# Нужно перебрать все числа вида x = 3**k * p**6, где p - простое число (кроме 3)

# Находим максимальное возможное k для отрезка через логарифм по основанию числа 3
k_max = int(math.log(7146924, 3))

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

# Перебираем простые числа от 2 до максимально возможного
for p in range(2, p_max + 1):
    if p != 3 and is_prime(p):  # Если число p - простое и не равно 3
        for k in range(k_max + 1):  # Перебираем до k_max включительно
            if 1732864 <= 3 ** k * p ** 6 <= 7146924:  # Проверяем, что итоговое число будет принадлежать отрезку
                ans += 1
print(ans)

Ответ: 6