Подтема 3 из 6
Числа с нужными делителями
Ровно k делителей, наибольшее количество делителей, величина M и наименьший делитель с его парой.
Ровно k делителей
Как найти числа, у которых ровно два делителя, не считая единицы и самого числа?
Перебрать числа, у каждого найти делители, отобрать нужные и сравнить их количество с двумя. Функция get_divisors из подтемы 2 делает самую трудную часть, остаётся перевести условие. Возьмём отрезок [10; 30], чтобы ответ можно было проверить в уме:
for n in range(10, 31): D = [d for d in get_divisors(n) if 1 < d < n] if len(D) == 2: print(n, D[0], D[1])У 10 без крайних остаются 2 и 5 — подходит. У 12 остаются 2, 3, 4, 6 — четыре, не подходит. У 27 остаются 3 и 9: подходит, хотя 9 не простое. «Два делителя» и «два простых делителя» — разные условия.
Для «ровно четыре чётных делителя» меняются только условие отбора и число: d % 2 == 0 и len(D) == 4. Само число тогда считается, если оно чётное: условие его не исключало.
Больше всего делителей
На отрезке [10; 30] найди число с наибольшим количеством делителей. Если таких несколько — наименьшее. Что нужно помнить по дороге?
Лучшее количество и число, у которого оно получилось. Новое число занимает их место, только если у него делителей больше.
best_count = 0best_number = 0for n in range(10, 31): count = count_divisors(n) if count > best_count: best_count = count best_number = n print(best_number, best_count)По восемь делителей у 24 и у 30. Перебор идёт по возрастанию, 24 встречается раньше, а строгое > не даёт 30 его заменить. Со знаком >= при равенстве побеждало бы более позднее число, и ответом стало бы 30. Знак выбирают по правилу «если таких несколько».
Величина M
В условии часто вводят букву: «M — сумма двух наибольших делителей числа, не считая единицы и самого числа; если таких делителей нет, M = 0». Как с ней работать?
M — просто величина, которую считают по списку делителей. Главное — прочитать определение дословно и не забыть случай, когда делителей не хватает.
n = 48D = [d for d in get_divisors(n) if 1 < d < n]if len(D) >= 2: M = D[-1] + D[-2]else: M = 0print(D, M)Два наибольших делителя 48 — 24 и 16, M = 40. Другие определения считаются по тому же списку D — выбери:
- сумма всех
sum(D)→ 75- наибольший − наименьший
D[-1] - D[0]→ 22- произведение двух наименьших
D[0] * D[1]→ 6- сумма трёх наибольших
sum(D[-3:])→ 52
Осторожнее с нулём. У простого числа делителей без 1 и n нет, M = 0, а 0 % 10 == 0 — истина. Если условие хочет M, оканчивающееся на 0, все простые числа пройдут проверку по ошибке. Поэтому пишут M > 0 and M % 10 == 0 — если, конечно, условие само не разрешает M = 0.
Наименьший и наибольший
M — сумма наименьшего и наибольшего делителей без единицы и самого числа. Нужен ли для неё весь список делителей?
Нет: наименьший делитель больше 1 и наибольший меньше n — это одна пара. Найди первый делитель, начиная с 2, — второй даст деление. На парах делителей 84 это видно сразу:
Дуги вложены друг в друга: чем левее начало, тем правее конец. Для 84 это 2 и 84 // 2 = 42, для 105 — 3 и 35.
def calc_m(n): for d in range(2, isqrt(n) + 1): if n % d == 0: return d + n // d return 0 print(calc_m(84), calc_m(105), calc_m(13))Перебор начинается с 2 — единица исключена — и останавливается на первом делителе: return сразу выходит из функции. У простого 13 делителей нет, функция вернёт 0. У 49 единственный такой делитель — 7, он и наименьший, и наибольший: M = 7 + 7 = 14, если условие не требует двух разных делителей.
Обоснование · необязательноПочему так для любого составного n
Пусть a — наименьший делитель n больше 1. Любой делитель b < n стоит в паре с n / b > 1, а чем больше один множитель пары, тем меньше другой. Самому маленькому a соответствует самый большой делитель меньше n — это n / a.
Первые после границы
Найди пять первых чисел больше 100, у которых M — сумма наименьшего и наибольшего делителей без 1 и n — оканчивается на 0. Как собрать программу?
Цикл из подтемы 1 — while found < 5 — с проверкой через calc_m внутри. Задачи этой подтемы так и устроены: перебор чисел снаружи, работа с делителями внутри.
n = 101found = 0while found < 5: M = calc_m(n) if M > 0 and M % 10 == 0: print(n, M) found += 1 n += 1111 = 3 · 37, M = 40. 125 = 5 · 25 — наибольший делитель 25 не простой, но условие о простоте ничего не говорит. Без M > 0 первым ответом стало бы простое 101.
На экзамене граница бывает и 700 000, и 5 000 000 — программа та же. calc_m обычно находит делитель за несколько шагов, до √n идёт только для простых чисел, поэтому перебор укладывается в секунды.
Итого
- Ровно kотобрать D и проверить
len(D) == k - Больше всегопомнить лучшее количество и число
- При равенстве«>» — первое из равных, «>=» — последнее
- Величина Mопределение дословно, M = 0 — проверить отдельно
- Наименьший и наибольшийодна пара: d и
n // d - Первые после N
while found < kиз подтемы 1
Проверьте себя
Ответь сначала сам, потом открой ответ.
ОтветСкрыть ответ
> на >=. Что она выведет?ОтветСкрыть ответ
ОтветСкрыть ответ
calc_m(91)? Сколько кандидатов d она проверит?ОтветСкрыть ответ
M > 0 and M % 10 == 0, а не просто M % 10 == 0?ОтветСкрыть ответ
Практика
Для проверки ответов нужен JavaScript. Условия, подсказки и решения доступны ниже.
Найди числа с четырьмя делителями от 20 до 40
Найди числа от 20 до 40, имеющие ровно четыре различных делителя без единицы и самого числа.
Запишите все строки ответа подряд в одну строку через пробел: в каждой строке число и его четыре делителя по возрастанию.
Подсказка
Для каждого числа отрезка оставь делители 1 < d < n и проверь, что их ровно четыре.
Решение
Подходят 20 (2, 4, 5, 10), 28 (2, 4, 7, 14) и 32 (2, 4, 8, 16).
Решение программой
from math import isqrt def get_divisors(n): divisors = [] for d in range(1, isqrt(n) + 1): if n % d == 0: divisors.append(d) q = n // d if q != d: divisors.append(q) return sorted(divisors) for n in range(20, 41): D = [d for d in get_divisors(n) if 1 < d < n] if len(D) == 4: print(n, *D)Программа выведет
20 2 4 5 1028 2 4 7 1432 2 4 8 16Ответ: 20 2 4 5 10 28 2 4 7 14 32 2 4 8 16
Выпиши пары делителей на отрезке
Найди среди чисел отрезка [235 400; 235 420] числа, у которых ровно два различных натуральных делителя, не считая единицы и самого числа. Для каждого найденного числа выведи эти два делителя в порядке возрастания; строки — в порядке возрастания чисел.
Запишите все строки ответа подряд в одну строку через пробел: в каждой строке два делителя по возрастанию.
Подсказка
Отбери делители 1 < d < n и проверь, что их ровно два. Само число выводить не нужно.
Решение
Подходят произведения двух разных простых и кубы простых. Например, 235 401 = 3 · 78 467.
Решение программой
from math import isqrt def get_divisors(n): divisors = [] for d in range(1, isqrt(n) + 1): if n % d == 0: divisors.append(d) if n // d != d: divisors.append(n // d) return sorted(divisors) for n in range(235400, 235421): D = [d for d in get_divisors(n) if 1 < d < n] if len(D) == 2: print(*D)Программа выведет
3 784672 1177017 336292 117703151 155911 214012 117709Ответ: 3 78467 2 117701 7 33629 2 117703 151 1559 11 21401 2 117709
Найди число с наибольшим количеством делителей
Среди чисел отрезка [1000; 1100] найди число с наибольшим количеством натуральных делителей. Если таких несколько, возьми наименьшее. Выведи количество делителей и само число.
Введите количество делителей и само число через пробел.
Подсказка
Храни лучший результат и заменяй его только при строго большем количестве — так при равенстве останется наименьшее число.
Решение
32 1080. На отрезке [1000; 1100] наибольшее количество делителей, 32, только у 1080.
Решение программой
from math import isqrt def count_divisors(n): count = 0 for d in range(1, isqrt(n) + 1): if n % d == 0: if d * d == n: count += 1 else: count += 2 return count best_count = 0best_n = 0for n in range(1000, 1101): count = count_divisors(n) if count > best_count: best_count = count best_n = nprint(best_count, best_n)Ответ: 32 1080
Вычисли M для числа 48
Пусть M — сумма двух наибольших различных делителей числа 48 без единицы и самого числа. Найди M.
Введите значение M.
Подсказка
Выпиши делители 48 без 1 и 48 по возрастанию; два наибольших стоят в конце.
Решение
Два наибольших подходящих делителя — 24 и 16, поэтому M = 40.
Решение программой
from math import isqrt def get_divisors(n): divisors = [] for d in range(1, isqrt(n) + 1): if n % d == 0: divisors.append(d) q = n // d if q != d: divisors.append(q) return sorted(divisors) D = [d for d in get_divisors(48) if 1 < d < 48]print(D[-1] + D[-2])Ответ: 40
Вычисли R по делителям на 8
Пусть R — сумма всех делителей числа, оканчивающихся на 8, не считая самого числа; если таких делителей нет, R = 0. Найди все числа отрезка [221 000; 221 040], для которых R оканчивается на 6. Для каждого выведи число и R.
Запишите все строки ответа подряд в одну строку через пробел: в каждой строке число и R.
Подсказка
Окончание на 8 — d % 10 == 8. R = 0 оканчивается на 0, так что числа без таких делителей отпадут сами.
Решение
Для каждого числа отрезка складываем делители, оканчивающиеся на 8 и не равные n, и проверяем последнюю цифру суммы.
Решение программой
from math import isqrt def get_divisors(n): divisors = [] for d in range(1, isqrt(n) + 1): if n % d == 0: divisors.append(d) if n // d != d: divisors.append(n // d) return sorted(divisors) for n in range(221000, 221041): D = get_divisors(n) R = sum(d for d in D if d % 10 == 8 and d != n) if R % 10 == 6: print(n, R)Программа выведет
221010 596221022 24576221024 27636221034 80376Ответ: 221010 596 221022 24576 221024 27636 221034 80376
Вычисли calc_m для трёх чисел
Чему равно calc_m(91), calc_m(97) и calc_m(121)?
Введите три значения через пробел: calc_m(91), calc_m(97), calc_m(121).
Подсказка
Наименьший делитель больше 1 и его пара — это наибольший делитель меньше n. Если такого делителя нет, функция возвращает 0.
Решение
20 (91 = 7·13), 0 (97 простое), 22 (у 121 единственный подходящий делитель 11, он и наименьший, и наибольший).
Решение программой
from math import isqrt def calc_m(n): for d in range(2, isqrt(n) + 1): if n % d == 0: return d + n // d return 0 print(calc_m(91), calc_m(97), calc_m(121))Ответ: 20 0 22
Найди близкие делители у чисел с четырьмя делителями
Рассматриваются числа, большие 800 000, у которых ровно четыре натуральных делителя. Найди шесть первых таких чисел, у которых наименьший и наибольший делители, не считая единицы и самого числа, отличаются не более чем на 15. Для каждого выведи число и эту разность.
Запишите все строки ответа подряд в одну строку через пробел: в каждой строке число и разность делителей.
Подсказка
Ровно четыре делителя: 1, a, b, n — между единицей и числом стоят ровно два, и нужна их разность b − a.
Решение
Например, 826 277 = 907 · 911: делители 1, 907, 911, 826 277, разность 911 − 907 = 4.
Решение программой
from math import isqrt def get_divisors(n): divisors = [] for d in range(1, isqrt(n) + 1): if n % d == 0: divisors.append(d) if n // d != d: divisors.append(n // d) return sorted(divisors) n = 800001found = 0while found < 6: D = get_divisors(n) if len(D) == 4 and D[2] - D[1] <= 15: print(n, D[2] - D[1]) found += 1 n += 1Программа выведет
826277 4833533 12837209 8853751 10870473 8874189 12Ответ: 826277 4 833533 12 837209 8 853751 10 870473 8 874189 12
Найди пять чисел с M, оканчивающимся на 6
Пусть M — сумма наименьшего и наибольшего натуральных делителей числа, не считая единицы и самого числа. Если таких делителей нет, M = 0. Найди пять наименьших чисел, больших 600 000, для которых M больше нуля и оканчивается цифрой 6. Для каждого выведи число и M.
Запишите все строки ответа подряд в одну строку через пробел: в каждой строке число и M.
Подсказка
M — это наименьший делитель больше 1 и его пара. Перебирай числа после 600 000 по возрастанию, пока не найдутся пять, — верхняя граница не нужна.
Решение
Проверка одной строки вручную: наименьший делитель 600 023, больший 1, — это 149, потому что 600 023 = 149 · 4027. Значит, M = 149 + 4027 = 4176, оно оканчивается на 6.
Решение программой
from math import isqrt def calc_m(n): for d in range(2, isqrt(n) + 1): if n % d == 0: return d + n // d return 0 n = 600001found = 0while found < 5: M = calc_m(n) if M > 0 and M % 10 == 6: print(n, M) found += 1 n += 1Программа выведет
600005 120006600008 300006600009 200006600023 4176600028 300016Ответ: 600005 120006 600008 300006 600009 200006 600023 4176 600028 300016
Найди пять чисел с M(N), кратным 101
Пусть M(N) — сумма двух наибольших различных натуральных делителей числа N, не считая единицы и самого N. Если таких делителей меньше двух, M(N) = 0. Найди пять наименьших чисел, больших 2 000 000, для которых M(N) больше нуля и делится на 101. Для каждого выведи N и M(N).
Запишите все строки ответа подряд в одну строку через пробел: в каждой строке N и M(N).
Подсказка
M(N) — сумма двух последних элементов отсортированного списка делителей без 1 и N. Если таких делителей меньше двух, M(N) = 0 и число не подходит.
Решение
Для каждого числа после 2 000 000 строим список делителей без 1 и N, складываем два наибольших и проверяем делимость на 101. Первые пять подходящих чисел — 2000103, 2000204, 2000305, 2000406 и 2000589.
Решение программой
from math import isqrt def get_divisors(n): divisors = [] for d in range(1, isqrt(n) + 1): if n % d == 0: divisors.append(d) q = n // d if q != d: divisors.append(q) return sorted(divisors) def calc_m(n): D = [d for d in get_divisors(n) if 1 < d < n] if len(D) < 2: return 0 return D[-1] + D[-2] n = 2000001found = 0while found < 5: M = calc_m(n) if M > 0 and M % 101 == 0: print(n, M) found += 1 n += 1Программа выведет
2000103 9524302000204 15001532000305 5177262000406 16670052000589 671852Ответ: 2000103 952430 2000204 1500153 2000305 517726 2000406 1667005 2000589 671852
Найди делители, оканчивающиеся на 14
Найди пять наименьших чисел, больших 600 000, у которых есть натуральный делитель, оканчивающийся на 14 и не равный ни самому числу, ни числу 14. Для каждого выведи число и наименьший такой делитель.
Запишите все строки ответа подряд в одну строку через пробел: в каждой строке число и наименьший подходящий делитель.
Подсказка
Окончание на 14 — это d % 100 == 14; исключи d == 14 и d == n. Делители отсортированы, поэтому наименьший — первый подходящий.
Решение
Например, у 600 028 делитель 300 014 = 600 028 / 2 оканчивается на 14, а меньших таких делителей нет.
Решение программой
from math import isqrt def get_divisors(n): divisors = [] for d in range(1, isqrt(n) + 1): if n % d == 0: divisors.append(d) if n // d != d: divisors.append(n // d) return sorted(divisors) n = 600001found = 0while found < 5: D = [d for d in get_divisors(n) if d % 100 == 14 and d != 14 and d != n] if D: print(n, D[0]) found += 1 n += 1Программа выведет
600028 300014600042 200014600054 314600056 214600070 120014Ответ: 600028 300014 600042 200014 600054 314 600056 214 600070 120014