Разбор задач

Гоша: Тимофей, недавно ты объяснял, что такое простые числа. Это числа, которые делятся без остатка только на 1 или на себя. Я решил написать функцию, которая определяет, является ли число простым.
Ряд простых чисел начинается с 2, ведь 1 не считается простым. 3 — простое число. Эти случаи можно обработать отдельно. Для других чисел будем выполнять проверку: если число nn делится без остатка на какое-то из чисел, меньших nn, но больших 1, то nn — составное.
Скопировать кодJSX
def is_prime(n):
    if n < 2:
        return False
    if n < 4:
        return True
    i = 2
    while i < n:
        if n % i == 0:
            return False
        i = i + 1
    return True
Тимофей: Алгоритм корректный. Но кажется, он будет долго работать.
Какая сложность предложенного алгоритма?
Тимофей: Можно решить эту задачу быстрее. Проверять числа, большие чем n\sqrt n не обязательно. Если у числа есть делитель, больший n\sqrt n, то есть и делитель, меньший n\sqrt n. А его мы проверим раньше.
Скопировать кодJSX
def is_prime(n):
    if n < 2:
        return False
    if n < 4:
        return True
    i = 2
    while i * i <= n:
        if n % i == 0:
            return False
        i = i + 1
    return True
Какая стала сложность алгоритма?
Гоша: Действительно. Все числа не нужно проверять. А почему ты написал i⋅i⩽ni \cdot i \leqslant n, а не i⩽ni \leqslant \sqrt n?
Тимофей: Операция вычисления корня очень дорогая. Вариант с умножением более эффективный.
Гоша: Спасибо. Нужно будет запомнить этот приём.
Кстати, с помощью функции is_prime(n) можно найти все простые числа, меньшие числа nn.
Для этого заведём пустой массив smaller_primes. Будем проверять все числа, меньшие nn, на простоту. Если число простое, добавим его в массив smaller_primes. В конце работы алгоритма в этом массиве будет содержаться ответ.
Скопировать кодJSX
def get_smaller_primes(n):
    smaller_primes = []
    for num in range(2, n):
        if is_prime(num):
            smaller_primes.append(num)
    return smaller_primes
Тимофей: Да, так можно определить все простые числа, не превосходящие n. Но этот метод не оптимальный. Его не стоит применять на практике.
Гоша: А какой метод более оптимальный?
Тимофей: Например, решето Эратосфена. Оно помогает найти все простые числа, не превосходящие nn.
Алгоритм такой:
  1. Выписываем все целые числа от 2 до nn.
  2. Заводим переменную num, равную первому не рассмотренному простому числу. Изначально она равна 2.
  3. Помечаем в списке числа от 2⋅num2 \cdot num до nn с шагом, равным num составными, то есть False. Например, для 2 пометим числа 4, 6, 8 и так далее.
  4. Находим первое не рассмотренное число в списке, большее чем num, и присваиваем переменной num это число.
  5. Повторяем два предыдущих шага, пока это возможно.
Код функции, реализующий решето Эратосфена:
Скопировать кодJSX
def eratosthenes(n):
    numbers = list(range(2, n + 1))
    for num in range(2, n):
        if is_prime(num):
            for j in range(2 * num, n + 1, num):
                numbers[j - 2] = False
    return numbers
Посмотрим, что вернёт функция, если вызвать её с n=9n=9.
Скопировать кодJSX
[2, 3, False, 5, False, 7, False, False]
Простые числа остались на своём месте. Там, где были составные числа, стоит False.
Алгоритм можно оптимизировать. Для каждого числа num начнём рассмотрение с числа p2p^2. Ведь все составные числа, меньшие него уже будут рассмотрены.
Получится такой код:
Скопировать кодJSX
def eratosthenes_effective(n):
    numbers = list(range(2, n + 1))
    for num in range(2, n):
        if is_prime(num):
            for j in range(num * num, n + 1, num):
                numbers[j - 2] = False
    return numbers
Рассмотрим подробно пример работы алгоритма для n=15n=15.
Скопировать кодJSX
2 3 4 5 6 7 8 9 10 11 12 13 14 15 # Запишем числа от 2 до 15

num = 2 # Пометим все числа, кратные 2, начиная с 4 False

2 3 False 5 False 7 False 9 False 11 False 13 False 15 

num = 3 # Пометим все числа, кратные 3, начиная с 9 False

2 3 False 5 False 7 False False False 11 False 13 False False False False

num = 3 Алгоритм можно завершить, так как num**2 больше 15.
Все числа, меньшие 15 кратные 5 уже рассмотрены.
Гоша: Интересный алгоритм, спасибо. Стало понятно, откуда название «решето». Мы как будто просеиваем числа, оставляя только простые. А есть ли еще более эффективный метод?
Тимофей: Решето Эратосфена работает за O(nlog⁡(log⁡n))O(n \log(\log n)). Чтобы это доказать, нужно знать некоторые более сложные факты из теории чисел, чем про которые я рассказывал. Глядя на код видно, что он работает не за линейное время. Существует метод решения задачи нахождения всех простых чисел, не превосходящих n, которому требуется O(n)O(n) операций. Метод называется линейное решето.
Алгоритм такой:
  1. Заведём массив sp (от smaller_primes) длины n+1n + 1. А также массив primes, в который будем добавлять найденные простые числа.
  2. Для каждого числа ii будем хранить sp[i] — минимальный простой делитель числа i.
  3. Перебираем ii по возрастанию.
  4. Если sp[i] = 0, можно сделать вывод, что число простое и добавить его в массив primes.
  5. Рассматриваем все простые числа p, которые не больше sp[i]. Обновляем sp[p * sp[i]] = p.
Скопировать кодJSX
def get_smaller_primes_linear(n):
    lp = [0] * (n + 1)
    primes = []
    for i in range(2, n):
        if lp[i] == 0:
            lp[i] = i
            primes.append(i)
        for p in primes:
            if (p > lp[i]) or (p * i > n):
                break
            lp[p * i] = p
    return primes, lp
Если вызвать функцию от 8, получим ([2, 3, 5, 7], [0, 0, 2, 3, 2, 5, 2, 7, 2]).
Первые два числа в массиве sp мы не затрагивали. Можно создать массив, длина которого на 2 меньше. В этом случае формула для индекса будет менее наглядной.
Основная идея в том, что к каждой ячейке массива sp мы обратимся не более одного раза. То есть сложность алгоритма линейная.
Решите задачи B, H, O: https://contest.yandex.ru/contest/19095/problems/