Тип 3
В предыдущих статьях мы прошли большой путь. Сначала познакомились с модулем fnmatch и научились решать задания первого типа, где требовалось находить числа по маске. Затем разобрались с эффективным поиском делителей числа, выяснили, почему достаточно перебирать только до корня, и научились быстро извлекать последние цифры числа.
Теперь мы подошли к самому сложному — третьему типу заданий. Здесь недостаточно просто найти делители числа. Нужно ещё определить, какие из них являются простыми числами. Это добавляет дополнительный слой сложности, ведь для каждого найденного делителя придётся выполнять проверку на простоту.
Давайте разберёмся, что такое простые числа и как эффективно проверять, является ли число простым.
Проверка простоты числа
Для начала вспомним, что такое простые числа. Простое число — это натуральное число больше единицы, которое делится нацело только на единицу и на само себя. Другими словами, у простого числа ровно два делителя.
Рассмотрим несколько примеров. Число 7 — простое, потому что делится только на 1 и на 7. Число 12 — составное, потому что помимо 1 и 12 делится ещё на 2, 3, 4 и 6. Число 2 — простое и, кстати, единственное чётное простое число. Все остальные чётные числа делятся на 2, а значит, не могут быть простыми.
Первые несколько простых чисел легко запомнить: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47…
Обратите внимание на важный момент: единица не считается простым числом. По определению, простое число должно иметь ровно два различных делителя, а у единицы делитель только один — она сама.
Простые числа называют «атомами» математики. Любое натуральное число можно разложить на произведение простых множителей, причём такое разложение единственно. Например, 60 = 2 × 2 × 3 × 5. Это фундаментальное свойство лежит в основе многих алгоритмов.
В задачах ЕГЭ простые числа встречаются регулярно. Вас могут попросить найти количество простых делителей числа, определить наибольший простой делитель или отобрать числа, у которых есть простой делитель с определёнными свойствами.
Самый очевидный способ проверить, является ли число простым — попробовать разделить его на все числа от 2 до этого числа минус один. Если ни одно деление не прошло нацело, число простое.
Но мы уже знаем из предыдущей статьи, что делители идут парами. Если число n делится на какое-то число m, то оно делится и на n/m. Причём один из этих делителей обязательно не превышает корня из n. Значит, достаточно проверить делимость только на числа от 2 до корня из n. Если среди них делителей не нашлось, число точно простое.
Можно пойти ещё дальше. Все чётные числа, кроме двойки, заведомо не являются простыми. Поэтому можно сначала отдельно проверить делимость на 2, а потом перебирать только нечётные числа. Это сокращает количество проверок вдвое.
Давайте напишем несколько вариантов функции проверки числа на простоту is_prime() и сравним их эффективность.
Обратите внимание, что подобные функции называются предикатами. Они принимают аргумент(ы) и проводят их проверку, возвращая всегда только логическое значение. Всегда следите за тем, какой тип данный возвращают ваши функции! Если функция предикат, то она возвращает только True или False.
Если функция возвращает какое-то число (как наши функции f() в программах ранее), то она должна возвращать только числовой тип данных: либо число, либо 0, а не False!
Но вернёмся к проверке числа на простоту. Начнём с самого простого подхода — перебираем все числа от 2 до n-1. Выглядеть это будет так:
Этот код максимально понятен. Если число меньше 2, оно не простое. Иначе перебираем все возможные делители. Как только нашли хотя бы один — возвращаем False. Если цикл завершился без нахождения делителей — число простое.
Но такой код крайне неэффективен. Давайте применим знание о парных делителях — будем проверять только до корня из числа.
Логика та же, но диапазон перебора значительно меньше. Для числа 1 000 000 вместо миллиона проверок делаем всего тысячу.
Идём еще дальше и добавим отдельную проверку на чётность. Теперь будем перебирать только нечётные числа.
Здесь мы сначала обрабатываем особые случаи: числа меньше 2 не простые, двойка — простое число, все остальные чётные — составные. После этого перебираем только нечётные числа, начиная с 3 и увеличивая счётчик на 2.
Но можно пойти ещё дальше и использовать интересную закономерность. Посмотрите на числа, которые не делятся ни на 2, ни на 3:
5, 7, 11, 13, 17, 19, 23, 25, 29, 31, 35, 37…
Заметьте, как они расположены относительно чисел, кратных шести:
- 6: 5, 7 (6-1 и 6+1)
- 12: 11, 13 (12-1 и 12+1)
- 18: 17, 19 (18-1 и 18+1)
- 24: 23, 25 (24-1 и 24+1)
- 30: 29, 31 (30-1 и 30+1)
Все числа, не делящиеся на 2 и на 3, находятся на расстоянии 1 от чисел, кратных шести. Математически их можно записать как 6k-1 и 6k+1, где k — натуральное число.
Почему так происходит? Давайте рассмотрим шесть последовательных чисел, начиная с любого кратного шести:
- 6k — делится на 6 (и на 2, и на 3)
- 6k+1 — не делится ни на 2, ни на 3
- 6k+2 — делится на 2
- 6k+3 — делится на 3
- 6k+4 — делится на 2
- 6k+5 — не делится ни на 2, ни на 3 (это то же самое, что 6(k+1)-1)
Из шести чисел только два могут быть простыми — те, что отстоят от кратного шести на единицу. Значит, при поиске делителей достаточно проверять только такие числа, пропуская все остальные.
Реализуем этот алгоритм в коде:
Разберём цикл подробнее. Мы начинаем с числа 5 (это 6×1-1) и на каждой итерации увеличиваем счётчик на 6. Получаем последовательность: 5, 11, 17, 23, 29… Это все числа вида 6k-1.
Внутри цикла мы проверяем делимость сразу на два числа: на div и на div + 2. Когда div равен 5, мы проверяем 5 и 7. Когда div равен 11, проверяем 11 и 13. Так мы охватываем все числа вида 6k-1 и 6k+1.
Вместо проверки каждого нечётного числа мы проверяем только каждое третье. Для больших чисел это даёт заметный выигрыш в скорости. Давайте продемонстрируем это и сравним, насколько отличается производительность этих функций. Создадим тест, который проверяет простоту всех чисел от 1 до 10 000.
Как видим, все, кроме наивного перебора до самого числа, справились неплохо. А самым же эффективным здесь является алгоритм с проверкой 6k±1 делителей.
Для заданий ЕГЭ вполне достаточно второго или третьего способа. Они просты для понимания и запоминания, а их производительности хватает с большим запасом. Но мы же для пущей эффективности будем применять четвёртый алгоритм.
Теперь объединим всё, что мы узнали за последние две статьи. Чтобы найти простые делители числа, нужно сначала найти все его делители, а затем отфильтровать среди них простые. В коде это можно записать так:
Функция get_prime_divisors() использует генератор множества: она берёт каждый делитель из результата get_divisors() и оставляет только те, для которых is_prime() возвращает True.
Проверим работу:
Число 60 раскладывается как 2 × 2 × 3 × 5, поэтому его простые делители — 2, 3 и 5. Число 100 = 2² × 5², простые делители — 2 и 5. А 97 само является простым числом, поэтому единственный его простой делитель — оно само.
Теперь у нас есть все инструменты для решения 25 заданий третьего типа.
Алгоритм решения
Начнём с такого задания:
«Напишите программу, которая перебирает целые числа, большие 1 324 727, в порядке возрастания и ищет среди них числа, представленные в виде произведения ровно двух простых множителей, не обязательно различных, каждый из которых содержит в своей записи ровно одну цифру 5.
В ответе в первом столбце таблицы запишите первые 5 найденных чисел в порядке возрастания, а во втором столбце — для каждого из чисел наибольший из соответствующих им найденных множителей.»
Давайте составим алгоритм действий:
- Перебираем числа от 1 324 728;
- Число должно раскладываться ровно на два простых множителя;
- Каждый множитель должен содержать в своей записи одну цифру 5.
Логично разбить всю нашу программу на несколько функций, каждая из которых отвечает за конкретную часть условия:
- Функция для проверки, содержит ли запись числа ровно одну цифру 5. Назовём её contains_5();
- Функция для проверки числа на простоту. Уже знакомая нам is_prime();
- И стандартная для нас функция f(), в которой будем искать два делителя числа, проверять, что оба простые и содержат цифру 5 с помощью функций из двух предыдущих пунктов.
Давайте приступать к решению. Первая функция будет самая простая — приводим аргумент к строчному типу данных и функцией count() считаем количество пятёрок в записи числа. Если оно равно единице, то возвращается истина, в остальных случаях — ложь. Запишем её так:
Дальше идёт is_prime(), для которой импортируем isqrt из модуля math:
Теперь напишем функцию f(). Здесь перебираем делители от 2 до корня из числа:
Если i является делителем, сразу определяем второй как num // i:
Всё, делители найдены, время проверить их на оба условия. Обратите внимания, что более быстрые проверки на наличие цифры 5 в записи числа следует расположить до более медленных на простоту.
В конце добавляем привычный нам цикл перебора чисел, в нём из задания в задание будут меняться только значения начала диапазона:
Запускаем программу и получаем 5 пар чисел для ответа:
1324795 264959
1324801 1151
1324903 2543
1325015 265003
1325029 5279
Пример 1
Рассмотрим еще одно похожее задание:
«Напишите программу, которая перебирает целые числа, большие 6 651 220, в порядке возрастания и ищет среди них числа, представленные в виде произведения ровно двух простых множителей, не обязательно различных, каждый из которых содержит в своей записи ровно одну цифру 2.
В ответе в первом столбце таблицы запишите первые 5 найденных чисел в порядке возрастания, а во втором столбце — для каждого из чисел соответствующий им наибольший из найденных множителей.»
Решение здесь будет практически идентичным. Поменяем первую функцию для проверки наличия цифры 2 в записи числа:
Остальное практически без изменений:
Запустим программу и увидим такие пары чисел:
6651241 2579
6651262 3325631
6651286 3325643
6651314 3325657
6651347 289189
Их и запишем в ответ.
Пример 2
Для закрепления рассмотрим еще одно задание:
«Пусть М — сумма минимального и максимального простых натуральных делителей целого числа, не считая самого числа. Если таких делителей у числа нет, то значение М считается равным нулю.
Напишите программу, которая перебирает целые числа, большие 5 400 000, в порядке возрастания и ищет среди них такие, для которых М больше 60 000 и является палиндромом, т.е. одинаково читается слева направо и справа налево.
В ответе запишите в первом столбце таблицы первые пять найденных чисел в порядке возрастания, а во втором столбце — соответствующие им значения М.
Например, для числа 298 M = 2 + 149 = 151.»
Это уже посложнее. Тут придётся немного переработать наш алгоритм.
Для начала напишем отдельную функцию для поиска делителей, она нам пригодится позже:
Далее напишем функцию-предикат для проверки числа на палиндром:
Здесь ничего сложного, запись числа должна равняться инвертированной записи. Например, для числа 121 функция is_palindrome() вернёт истину.
Затем идёт функция для проверки числа на простоту:
И дальше начинаются нововведения в стандартную функцию f(). Создадим отдельный список со всеми простыми делителями числа num:
Если таких делителей нет, то сразу возвращаем 0:
Теперь формируем число M как сумму максимального и минимального простых делителей. И проверяем, что это M больше 60 000 и является палиндромом. Если условие истинно, возвращаем М, если нет — 0:
А цикл без изменений:
Запускаем нашу программу и получаем пятёрку пар чисел:
5400042 900009
5400420 90009
5400866 158851
5406116 1351531
5406420 90109
Они и будут ответом на данное задание.
<<< Предыдущая статья Первая статья >>>
Больше заданий данного типа с подробным решением вы можете найти в нашем тренажёре.