Навигация по странице
Тип 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. Выглядеть это будет так:
def is_prime_naive(n):
if n < 2:
return False
for i in range(2, n):
if n % i == 0:
return False
return True
Этот код максимально понятен. Если число меньше 2, оно не простое. Иначе перебираем все возможные делители. Как только нашли хотя бы один — возвращаем False. Если цикл завершился без нахождения делителей — число простое.
Но такой код крайне неэффективен. Давайте применим знание о парных делителях — будем проверять только до корня из числа.
from math import isqrt
def is_prime_sqrt(n):
if n < 2:
return False
for i in range(2, isqrt(n) + 1):
if n % i == 0:
return False
return True
Логика та же, но диапазон перебора значительно меньше. Для числа 1 000 000 вместо миллиона проверок делаем всего тысячу.
Идём еще дальше и добавим отдельную проверку на чётность. Теперь будем перебирать только нечётные числа.
from math import isqrt
def is_prime_odd(n):
if n < 2:
return False
if n == 2:
return True
if n % 2 == 0:
return False
for i in range(3, isqrt(n) + 1, 2):
if n % i == 0:
return False
return True
Здесь мы сначала обрабатываем особые случаи: числа меньше 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)
Из шести чисел только два могут быть простыми — те, что отстоят от кратного шести на единицу. Значит, при поиске делителей достаточно проверять только такие числа, пропуская все остальные.
Реализуем этот алгоритм в коде:
from math import isqrt
def is_prime_6k(n):
if n < 2:
return False
if n == 2:
return True
if n % 2 == 0:
return False
if n == 3:
return True
if n % 3 == 0:
return False
for div in range(5, isqrt(n) + 1, 6):
if n % div == 0 or n % (div + 2) == 0:
return False
return True
Разберём цикл подробнее. Мы начинаем с числа 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.
from timeit import timeit
from math import isqrt
def is_prime_naive(n):
if n < 2:
return False
for i in range(2, n):
if n % i == 0:
return False
return True
def is_prime_sqrt(n):
if n < 2:
return False
for i in range(2, isqrt(n) + 1):
if n % i == 0:
return False
return True
def is_prime_odd(n):
if n < 2:
return False
if n == 2:
return True
if n % 2 == 0:
return False
for i in range(3, isqrt(n) + 1, 2):
if n % i == 0:
return False
return True
def is_prime_6k(n):
if n < 2:
return False
if n == 2:
return True
if n % 2 == 0:
return False
if n == 3:
return True
if n % 3 == 0:
return False
for div in range(5, isqrt(n) + 1, 6):
if n % div == 0 or n % (div + 2) == 0:
return False
return True
def test_naive():
for n in range(1, 10_001):
is_prime_naive(n)
def test_sqrt():
for n in range(1, 10_001):
is_prime_sqrt(n)
def test_odd():
for n in range(1, 10_001):
is_prime_odd(n)
def test_6k():
for n in range(1, 10_001):
is_prime_6k(n)
t1 = timeit(test_naive, number=10)
t2 = timeit(test_sqrt, number=10)
t3 = timeit(test_odd, number=10)
t4 = timeit(test_6k, number=10)
print(f'Наивный перебор: {t1 * 1000:.2f} мс')
print(f'До корня: {t2 * 1000:.2f} мс')
print(f'Только нечётные: {t3 * 1000:.2f} мс')
print(f'Оптимизация 6k±1: {t4 * 1000:.2f} мс')
>>>Наивный перебор: 3239.88 мс
>>>До корня: 76.21 мс
>>>Только нечётные: 50.79 мс
>>>Оптимизация 6k±1: 44.74 мс
Как видим, все, кроме наивного перебора до самого числа, справились неплохо. А самым же эффективным здесь является алгоритм с проверкой 6k±1 делителей.
Для заданий ЕГЭ вполне достаточно второго или третьего способа. Они просты для понимания и запоминания, а их производительности хватает с большим запасом. Но мы же для пущей эффективности будем применять четвёртый алгоритм.
Теперь объединим всё, что мы узнали за последние две статьи. Чтобы найти простые делители числа, нужно сначала найти все его делители, а затем отфильтровать среди них простые. В коде это можно записать так:
from math import isqrt
def is_prime(n):
if n < 2:
return False
if n == 2:
return True
if n % 2 == 0:
return False
if n == 3:
return True
if n % 3 == 0:
return False
for div in range(5, isqrt(n) + 1, 6):
if n % div == 0 or n % (div + 2) == 0:
return False
return True
def get_divisors(num):
divisors = set()
for i in range(1, isqrt(num) + 1):
if num % i == 0:
divisors |= {i, num // i}
return divisors
def get_prime_divisors(num):
return {d for d in get_divisors(num) if is_prime(d)}
Функция get_prime_divisors() использует генератор множества: она берёт каждый делитель из результата get_divisors() и оставляет только те, для которых is_prime() возвращает True.
Проверим работу:
print(get_prime_divisors(60))
print(get_prime_divisors(100))
print(get_prime_divisors(97))
>>>{2, 3, 5}
>>>{2, 5}
>>>{97}
Число 60 раскладывается как 2 × 2 × 3 × 5, поэтому его простые делители — 2, 3 и 5. Число 100 = 2² × 5², простые делители — 2 и 5. А 97 само является простым числом, поэтому единственный его простой делитель — оно само.
Теперь у нас есть все инструменты для решения 25 заданий третьего типа.
Алгоритм решения
Начнём с такого задания:
Задание 2516
«Напишите программу, которая перебирает целые числа, большие 1 324 727, в порядке возрастания и ищет среди них числа, представленные в виде произведения ровно двух простых множителей, не обязательно различных, каждый из которых содержит в своей записи ровно одну цифру 5.
В ответе в первом столбце таблицы запишите первые 5 найденных чисел в порядке возрастания, а во втором столбце — для каждого из чисел наибольший из соответствующих им найденных множителей.»
Давайте составим алгоритм действий:
- Перебираем числа от 1 324 728;
- Число должно раскладываться ровно на два простых множителя;
- Каждый множитель должен содержать в своей записи одну цифру 5.
Логично разбить всю нашу программу на несколько функций, каждая из которых отвечает за конкретную часть условия:
- Функция для проверки, содержит ли запись числа ровно одну цифру 5. Назовём её contains_5();
- Функция для проверки числа на простоту. Уже знакомая нам is_prime();
- И стандартная для нас функция f(), в которой будем искать два делителя числа, проверять, что оба простые и содержат цифру 5 с помощью функций из двух предыдущих пунктов.
Давайте приступать к решению. Первая функция будет самая простая — приводим аргумент к строчному типу данных и функцией count() считаем количество пятёрок в записи числа. Если оно равно единице, то возвращается истина, в остальных случаях — ложь. Запишем её так:
def contains_5(num):
return str(num).count('5') == 1
Дальше идёт is_prime(), для которой импортируем isqrt из модуля math:
from math import isqrt
def contains_5(num):
return str(num).count('5') == 1
def is_prime(num):
if num < 2:
return False
if num == 2:
return True
if num % 2 == 0:
return False
if num == 3:
return True
if num % 3 == 0:
return False
for div in range(5, isqrt(num) + 1, 6):
if num % div == 0 or num % (div + 2) == 0:
return False
return True
Теперь напишем функцию f(). Здесь перебираем делители от 2 до корня из числа:
from math import isqrt
def contains_5(num):
return str(num).count('5') == 1
def is_prime(num):
if num < 2:
return False
if num == 2:
return True
if num % 2 == 0:
return False
if num == 3:
return True
if num % 3 == 0:
return False
for div in range(5, isqrt(num) + 1, 6):
if num % div == 0 or num % (div + 2) == 0:
return False
return True
def f(num):
for i in range(2, isqrt(num) + 1):
Если i является делителем, сразу определяем второй как num // i:
from math import isqrt
def contains_5(num):
return str(num).count('5') == 1
def is_prime(num):
if num < 2:
return False
if num == 2:
return True
if num % 2 == 0:
return False
if num == 3:
return True
if num % 3 == 0:
return False
for div in range(5, isqrt(num) + 1, 6):
if num % div == 0 or num % (div + 2) == 0:
return False
return True
def f(num):
for i in range(2, isqrt(num) + 1):
if num % i == 0:
j = num // i
Всё, делители найдены, время проверить их на оба условия. Обратите внимания, что более быстрые проверки на наличие цифры 5 в записи числа следует расположить до более медленных на простоту.
from math import isqrt
def contains_5(num):
return str(num).count('5') == 1
def is_prime(num):
if num < 2:
return False
if num == 2:
return True
if num % 2 == 0:
return False
if num == 3:
return True
if num % 3 == 0:
return False
for div in range(5, isqrt(num) + 1, 6):
if num % div == 0 or num % (div + 2) == 0:
return False
return True
def f(num):
for i in range(2, isqrt(num) + 1):
if num % i == 0:
j = num // i
if contains_5(i) and contains_5(j) and is_prime(i) and is_prime(j):
return max(i, j)
return 0
В конце добавляем привычный нам цикл перебора чисел, в нём из задания в задание будут меняться только значения начала диапазона:
from math import isqrt
def contains_5(num):
return str(num).count('5') == 1
def is_prime(num):
if num < 2:
return False
if num == 2:
return True
if num % 2 == 0:
return False
if num == 3:
return True
if num % 3 == 0:
return False
for div in range(5, isqrt(num) + 1, 6):
if num % div == 0 or num % (div + 2) == 0:
return False
return True
def f(num):
for i in range(2, isqrt(num) + 1):
if num % i == 0:
j = num // i
if contains_5(i) and contains_5(j) and is_prime(i) and is_prime(j):
return max(i, j)
return 0
cnt = 0
for i in range(1_324_729, 10 ** 20):
if M := f(i):
print(i, M)
cnt += 1
if cnt == 5:
break
Запускаем программу и получаем 5 пар чисел для ответа:
1324795 264959
1324801 1151
1324903 2543
1325015 265003
1325029 5279
Пример 1
Рассмотрим еще одно похожее задание:
Задание 2518
«Напишите программу, которая перебирает целые числа, большие 6 651 220, в порядке возрастания и ищет среди них числа, представленные в виде произведения ровно двух простых множителей, не обязательно различных, каждый из которых содержит в своей записи ровно одну цифру 2.
В ответе в первом столбце таблицы запишите первые 5 найденных чисел в порядке возрастания, а во втором столбце — для каждого из чисел соответствующий им наибольший из найденных множителей.»
Решение здесь будет практически идентичным. Поменяем первую функцию для проверки наличия цифры 2 в записи числа:
from math import isqrt
def contains_2(num):
return str(num).count('2') == 1
Остальное практически без изменений:
from math import isqrt
def contains_2(num):
return str(num).count('2') == 1
def is_prime(num):
if num < 2:
return False
if num == 2:
return True
if num % 2 == 0:
return False
if num == 3:
return True
if num % 3 == 0:
return False
for div in range(5, isqrt(num) + 1, 6):
if num % div == 0 or num % (div + 2) == 0:
return False
return True
def f(num):
for i in range(2, isqrt(num) + 1):
if num % i == 0:
j = num // i
if contains_2(i) and contains_2(j) and is_prime(i) and is_prime(j):
return max(i, j)
return 0
cnt = 0
for i in range(6_651_221, 10 ** 20):
if M := f(i):
print(i, M)
cnt += 1
if cnt == 5:
break
Запустим программу и увидим такие пары чисел:
6651241 2579
6651262 3325631
6651286 3325643
6651314 3325657
6651347 289189
Их и запишем в ответ.
Пример 2
Для закрепления рассмотрим еще одно задание:
Задание 2517
«Пусть М — сумма минимального и максимального простых натуральных делителей целого числа, не считая самого числа. Если таких делителей у числа нет, то значение М считается равным нулю.
Напишите программу, которая перебирает целые числа, большие 5 400 000, в порядке возрастания и ищет среди них такие, для которых М больше 60 000 и является палиндромом, т.е. одинаково читается слева направо и справа налево.
В ответе запишите в первом столбце таблицы первые пять найденных чисел в порядке возрастания, а во втором столбце — соответствующие им значения М.
Например, для числа 298 M = 2 + 149 = 151.»
Это уже посложнее. Тут придётся немного переработать наш алгоритм.
Для начала напишем отдельную функцию для поиска делителей, она нам пригодится позже:
from math import isqrt
def get_divisors(num):
divisors = set()
for i in range(2, isqrt(num) + 1):
if num % i == 0:
divisors |= {i, num // i}
return divisors
Далее напишем функцию-предикат для проверки числа на палиндром:
from math import isqrt
def get_divisors(num):
divisors = set()
for i in range(2, isqrt(num) + 1):
if num % i == 0:
divisors |= {i, num // i}
return divisors
def is_palindrome(num):
s = str(num)
return s == s[::-1]
Здесь ничего сложного, запись числа должна равняться инвертированной записи. Например, для числа 121 функция is_palindrome() вернёт истину.
Затем идёт функция для проверки числа на простоту:
from math import isqrt
def get_divisors(num):
divisors = set()
for i in range(2, isqrt(num) + 1):
if num % i == 0:
divisors |= {i, num // i}
return divisors
def is_palindrome(num):
s = str(num)
return s == s[::-1]
def is_prime(num):
if num < 2:
return False
if num == 2:
return True
if num % 2 == 0:
return False
if num == 3:
return True
if num % 3 == 0:
return False
for div in range(5, isqrt(num) + 1, 6):
if num % div == 0 or num % (div + 2) == 0:
return False
return True
И дальше начинаются нововведения в стандартную функцию f(). Создадим отдельный список со всеми простыми делителями числа num:
from math import isqrt
def get_divisors(num):
divisors = set()
for i in range(2, isqrt(num) + 1):
if num % i == 0:
divisors |= {i, num // i}
return divisors
def is_palindrome(num):
s = str(num)
return s == s[::-1]
def is_prime(num):
if num < 2:
return False
if num == 2:
return True
if num % 2 == 0:
return False
if num == 3:
return True
if num % 3 == 0:
return False
for div in range(5, isqrt(num) + 1, 6):
if num % div == 0 or num % (div + 2) == 0:
return False
return True
def f(num):
divisors = [div for div in get_divisors(num) if is_prime(div)]
Если таких делителей нет, то сразу возвращаем 0:
from math import isqrt
def get_divisors(num):
divisors = set()
for i in range(2, isqrt(num) + 1):
if num % i == 0:
divisors |= {i, num // i}
return divisors
def is_palindrome(num):
s = str(num)
return s == s[::-1]
def is_prime(num):
if num < 2:
return False
if num == 2:
return True
if num % 2 == 0:
return False
if num == 3:
return True
if num % 3 == 0:
return False
for div in range(5, isqrt(num) + 1, 6):
if num % div == 0 or num % (div + 2) == 0:
return False
return True
def f(num):
divisors = [div for div in get_divisors(num) if is_prime(div)]
if not divisors:
return 0
Теперь формируем число M как сумму максимального и минимального простых делителей. И проверяем, что это M больше 60 000 и является палиндромом. Если условие истинно, возвращаем М, если нет — 0:
from math import isqrt
def get_divisors(num):
divisors = set()
for i in range(2, isqrt(num) + 1):
if num % i == 0:
divisors |= {i, num // i}
return divisors
def is_palindrome(num):
s = str(num)
return s == s[::-1]
def is_prime(num):
if num < 2:
return False
if num == 2:
return True
if num % 2 == 0:
return False
if num == 3:
return True
if num % 3 == 0:
return False
for div in range(5, isqrt(num) + 1, 6):
if num % div == 0 or num % (div + 2) == 0:
return False
return True
def f(num):
divisors = [div for div in get_divisors(num) if is_prime(div)]
if not divisors:
return 0
M = min(divisors) + max(divisors)
if M > 60_000 and is_palindrome(M):
return M
return 0
А цикл без изменений:
from math import isqrt
def get_divisors(num):
divisors = set()
for i in range(2, isqrt(num) + 1):
if num % i == 0:
divisors |= {i, num // i}
return divisors
def is_palindrome(num):
s = str(num)
return s == s[::-1]
def is_prime(num):
if num < 2:
return False
if num == 2:
return True
if num % 2 == 0:
return False
if num == 3:
return True
if num % 3 == 0:
return False
for div in range(5, isqrt(num) + 1, 6):
if num % div == 0 or num % (div + 2) == 0:
return False
return True
def f(num):
divisors = [div for div in get_divisors(num) if is_prime(div)]
if not divisors:
return 0
M = min(divisors) + max(divisors)
if M > 60_000 and is_palindrome(M):
return M
return 0
cnt = 0
for i in range(5_400_001, 10 ** 20):
if M := f(i):
print(i, M)
cnt += 1
if cnt == 5:
break
Запускаем нашу программу и получаем пятёрку пар чисел:
5400042 900009
5400420 90009
5400866 158851
5406116 1351531
5406420 90109
Они и будут ответом на данное задание.