Задание 25: обработка целых чисел (делители, НОД, факторизация)

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

Собственный делитель числа n — любой его делитель, кроме самого n. Наибольший собственный делитель равен n, делённому на наименьший простой делитель.

Что проверяет задание 25

Задание 25 — повышенный уровень, 1 балл. Дан диапазон целых чисел. Нужно отобрать числа по свойству, связанному с делителями: «имеют ровно K делителей», «у которых наибольший собственный делитель оканчивается на …», «делятся на своё число цифр» и т. п. Для каждого подходящего числа часто выводят дополнительную характеристику (наибольший делитель, число делителей).

Теория: делители и перебор до корня

Делитель числа n — это d, при котором n делится на d без остатка. Делители идут парами: если d делит n, то и n/d делит n. Поэтому достаточно перебрать d от 1 до ⌊√n⌋ — каждый найденный d даёт пару (d, n/d). Это превращает перебор из O(n) в O(√n), что критично для больших чисел.

для d от 1 до корня из n:
    если n делится на d:
        d — делитель, и n/d — тоже делитель

Наибольший собственный делитель удобно искать через наименьший простой делитель p: наибольший собственный делитель = n / p. Если у n нет делителя ≤ √n (кроме 1), значит n простое и его наибольший собственный делитель — 1.

Метод решения

1. Напишите функцию-помощник (число делителей или наибольший собственный делитель) с перебором до корня.
2. Пройдите по числам диапазона и отберите подходящие.
3. Выведите нужную характеристику для каждого (или их количество/сумму).

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

Для чисел диапазона нужно вывести их наибольший собственный делитель. Покажем на диапазоне 100–109 (на экзамене диапазон шире и читается из условия).

Решение на Python

def largest_proper_divisor(n):
    "Наибольший собственный делитель = n / (наименьший простой делитель)."
    d = 2
    while d * d <= n:
        if n % d == 0:
            return n // d        # наименьший делитель d, ответ равен n/d
        d += 1
    return 1                     # делителей до корня нет -> n простое

for n in range(100, 110):
    print(n, "наибольший собственный делитель:", largest_proper_divisor(n))

Вывод:

100 наибольший собственный делитель: 50
101 наибольший собственный делитель: 1
102 наибольший собственный делитель: 51
103 наибольший собственный делитель: 1
104 наибольший собственный делитель: 52
105 наибольший собственный делитель: 35
106 наибольший собственный делитель: 53
107 наибольший собственный делитель: 1
108 наибольший собственный делитель: 54
109 наибольший собственный делитель: 1

Для 100 наименьший простой делитель — 2, значит наибольший собственный — 100/2 = 50. Для 105 наименьший — 3, ответ 105/3 = 35. Простые числа (101, 103, 107, 109) дают 1.

Подсчёт числа делителей

Сколько у числа всего делителей — частый вопрос (например, «отобрать числа ровно с 6 делителями»). Считаем парами до корня, аккуратно с полным квадратом.

def num_divisors(n):
    count = 0
    d = 1
    while d * d <= n:
        if n % d == 0:
            count += 1 if d * d == n else 2   # пара (d, n/d); квадрат — один раз
        d += 1
    return count

# Числа в диапазоне ровно с 6 делителями
result = [n for n in range(2, 60) if num_divisors(n) == 6]
print("Числа с 6 делителями:", result)

Вывод:

Числа с 6 делителями: [12, 18, 20, 28, 32, 44, 45, 50, 52]

НОД через алгоритм Евклида

Если в задаче встречается наибольший общий делитель, берите готовый math.gcd или алгоритм Евклида.

from math import gcd
print("НОД(48, 36) =", gcd(48, 36))
print("НОД(100, 75) =", gcd(100, 75))

Вывод:

НОД(48, 36) = 12
НОД(100, 75) = 25

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

• Перебор до n вместо √n. Для больших чисел это медленно; перебирайте делители до корня.
• Дважды считают делитель полного квадрата. Для n = d² пара (d, n/d) — это одно и то же число, считать один раз.
• Путают «собственный» и «любой» делитель. Собственный — кроме самого числа; единица обычно считается собственным делителем.
• Забывают про простые числа. У простого наибольший собственный делитель — 1.

Итог

• Делители ищут до √n: каждый d даёт пару (d, n/d) — это ускоряет перебор.
• Наибольший собственный делитель = n / (наименьший простой делитель); у простого — 1.
• Число делителей считают парами с поправкой на полный квадрат; НОД — через math.gcd.