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

Просмотров 8 Комментарии 0

Напишите программу, которая ищет среди целых чисел, принадлежащих числовому отрезку $[123456789;987654321]$ , числа, имеющие ровно $11$ натуральных делителей. Напишите в ответ все такие числа через пробел в порядке возрастания.

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

В данной задаче необходимо, чтобы у числа было ровно 11 натуральных делителей.

Тогда произведение всех $qi$ должно быть равно 11. Так как число 11 – простое, то только 1 множитель должен быть равен 11. Отсюда некоторое $q = 10 i$ .

Тогда число имеет вид $10 p$ где $p$ – любое простое число.

Таким образом, нужно будет перебрать простые числа так, чтобы получить все возможные числа вида $p10$ из отрезка $[123456789;987654321]$ .

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 = []  # Список чисел для ответа

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

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

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

print(*sorted(ans)) # Выводим ответ в порядке возрастания

Ответ: 282475249