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

Напишите программу, которая ищет среди целых чисел, принадлежащих числовому отрезку $[1234567;7654321]$ , числа, у которых ровно $7$ делителей, сумма цифр которых некратна $3$ . Количество делителей, чья сумма цифр кратна $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(7654321, 3))

# Находим максимально возможное p для отрезка
p_max = int(7654321 ** (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 1234567 <= 3 ** k * p ** 6 <= 7654321:  # Проверяем, что итоговое число будет принадлежать отрезку
                ans += 1
print(ans)

Ответ: 8