Что спрашивают

На включённом отрезке [A; B] найдите числа, у которых ровно два различных делителя, если не считать 1 и само число. Для каждого найденного числа выведите только два этих делителя по возрастанию.

Строки упорядочиваются по произведению выведенных делителей. Само найденное число печатать не нужно. B не больше 10^9, ширина отрезка не больше 1000; подходящее число существует.

Приём решения

Переберём пары делителей d и n // d, начиная с d = 2. Оба являются нетривиальными. Если они совпадают, запишем только один: условие считает различные делители.

  1. Для каждого n от A до B включительно соберите нетривиальные делители по парам.
  2. Как только их стало больше двух, можно отвергнуть n, не продолжая проверку.
  3. Если после полного перебора их ровно два, отсортируйте эту пару и добавьте в ответ.

Какие числа вообще подходят? У них четыре делителя вместе с 1 и n. Это произведение разных простых p × q или куб простого p³. Во втором случае нужная пара равна p и p². Квадрат простого имеет только один нетривиальный делитель и не подходит.

В обоих допустимых случаях произведение нужных делителей равно n. Поэтому проход по n по возрастанию уже обеспечивает требуемый порядок строк. Сортировка всех пар по первому делителю дала бы другой порядок.

На отрезке ширины W проверка требует не более O(W√B) операций, обычно меньше благодаря раннему отказу. Для одного числа сохраняется не более нескольких делителей; множество всех делителей строить не нужно.

Разбор на примере

Ввод

25 40

Вывод

2 13
3 9
3 11
2 17
5 7
2 19
3 13
Разбор примера по шагам
ЧислоНетривиальные делителиПроверка
255Только один
262, 13Подходит
273, 9Подходит: куб простого
322, 4, 8, 16Слишком много
333, 11Подходит
342, 17Подходит
355, 7Подходит
382, 19Подходит
393, 13Подходит

Подходят 26, 27, 33, 34, 35, 38 и 39. Их выведенные пары не упорядочены по первому элементу, но произведения равны найденным числам и возрастают. Число 25 исключается, хотя оно составное: у него лишь один различный нетривиальный делитель.

Код на Python и C++

Вывод содержит именно два делителя. Проход по числам сохраняет порядок их произведений, поэтому общая сортировка результата не нужна.

В C++ функция возвращает пустой vector, если нетривиальных делителей не ровно два: это замена None.

import sys
from math import isqrt


def proper_pair(n):
    divisors = []
    for d in range(2, isqrt(n) + 1):
        if n % d == 0:
            divisors.append(d)
            other = n // d
            if other != d:
                divisors.append(other)
            if len(divisors) > 2:
                return None
    return tuple(sorted(divisors)) if len(divisors) == 2 else None


def solve(a, b):
    rows = []
    for n in range(a, b + 1):
        pair = proper_pair(n)
        if pair is not None:
            rows.append(pair)
    return rows

if __name__ == '__main__':
    a, b = map(int, sys.stdin.read().split())
    rows = solve(a, b)
    for row in rows:
        print(*row)
#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;

// Возвращает нетривиальные делители n, если их ровно два, иначе пустой список.
vector<long long> proper_pair(long long n) {
    vector<long long> divisors;
    for (long long d = 2; d * d <= n; d++) {
        if (n % d == 0) {
            divisors.push_back(d);
            long long other = n / d;
            if (other != d)
                divisors.push_back(other);
            if (divisors.size() > 2)
                return {};
        }
    }
    if (divisors.size() != 2)
        return {};
    sort(divisors.begin(), divisors.end());
    return divisors;
}

int main() {
    long long a, b;
    cin >> a >> b;
    for (long long n = a; n <= b; n++) {
        vector<long long> pair = proper_pair(n);
        if (!pair.empty())
            cout << pair[0] << ' ' << pair[1] << '\n';
    }
}

Типичные ошибки

  • Забыть кубы простых

    У p³ ровно два нетривиальных делителя: p и p². Требовать только произведение разных простых нельзя.

  • Посчитать корень квадрата дважды

    Делители должны быть различными. Пара d и n // d с равными элементами добавляется один раз.

  • Вывести само число перед парой

    В этой задаче формат ответа содержит только два делителя. Следуйте указанным столбцам вывода.

  • Отсортировать строки по первому делителю

    Требуется порядок произведений. Его уже даёт перебор n по возрастанию.