Что спрашивают
На включённом отрезке [A; B] найдите числа, у которых ровно два различных делителя, если не считать 1 и само число. Для каждого найденного числа выведите только два этих делителя по возрастанию.
Строки упорядочиваются по произведению выведенных делителей. Само найденное число печатать не нужно. B не больше 10^9, ширина отрезка не больше 1000; подходящее число существует.
Приём решения
Переберём пары делителей d и n // d, начиная с d = 2. Оба являются нетривиальными. Если они совпадают, запишем только один: условие считает различные делители.
- Для каждого n от A до B включительно соберите нетривиальные делители по парам.
- Как только их стало больше двух, можно отвергнуть n, не продолжая проверку.
- Если после полного перебора их ровно два, отсортируйте эту пару и добавьте в ответ.
Какие числа вообще подходят? У них четыре делителя вместе с 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
| Число | Нетривиальные делители | Проверка |
|---|---|---|
| 25 | 5 | Только один |
| 26 | 2, 13 | Подходит |
| 27 | 3, 9 | Подходит: куб простого |
| 32 | 2, 4, 8, 16 | Слишком много |
| 33 | 3, 11 | Подходит |
| 34 | 2, 17 | Подходит |
| 35 | 5, 7 | Подходит |
| 38 | 2, 19 | Подходит |
| 39 | 3, 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)
<algorithm>
<iostream>
<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 по возрастанию.