ЕГЭ Информатика 2021: Задача 25 — числа с двумя делителями

Программа находит целые числа в диапазоне от 174000457 до 17404505 включительно, имеющие ровно два различных натуральных делителя (не считая единицы и самого числа). Для каждого найденного числа выводятся эти два делителя в порядке возрастания.

Постановка задачи

Задача сводится к проверке делимости чисел. Число, имеющее ровно два делителя помимо единицы и самого себя, представляет собой квадрат простого числа. Выводятся пары делителей, упорядоченные по возрастанию их произведения. Пример: в диапазоне от 5 до 9 такие числа – 6 (2 * 3) и 8 (2 * 4).

Решение на языке Python

Программа на Python решает задачу следующим образом:

  1. Определение диапазона:

    for n in range(174000457, 17404506):

    Цикл for перебирает числа в диапазоне от 174000457 до 17404505 включительно.

  2. Поиск делителей:

    deliтели = []
    for d in range(2, int(n**0.5) + 1):
        if n % d == 0:
            deliтели.extend([d, n // d])
            break

    Вложенный цикл перебирает потенциальные делители от 2 до квадратного корня из n. Если n делится на d без остатка, то d и n // d являются делителями. Список deliтели дополняется найденными делителями, после чего цикл прерывается.

  3. Вывод результата:

    if len(deliтели) == 2:
        print(min(deliтели), max(deliтели))

    Если найдено два делителя, они выводятся в порядке возрастания.

Программа эффективно находит числа в заданном диапазоне, имеющие ровно два делителя (помимо 1 и самого числа), и выводит эти делители. Обратите внимание на оптимизацию поиска делителей с использованием квадратного корня.

Что будем искать? Например,программа