EPI: оптимизированный алгоритм генерации простых чисел

Question

Я сейчас прохожу "Элементы программирования Интервью" в python и застрял в этой части. Код ниже генерирует простые числа до n. Объяснение скорее отсутствует, и у меня нет математического фона, чтобы понять его.

Мы можем улучшить время выполнения, просеивая кратные p от p ^ 2 вместо p, так как все числа форма kp, где k

Код ниже:

def generate_primesII(n):

    if n < 2:
        return []

    size = (n - 3) // 2 + 1
    primes = [2]  # stores the primes from 1 to n

    # is_prime[i] represents (2i + 2) is prime or not
    # Initially set each to true. Then use sieving to eliminate nonprimes
    is_prime = [True] * size

    for i in range(size):
        if is_prime[i]:

            p = i * 2 + 3
            primes.append(p)

            # Sieving from p^2, where p^2 = (4i^2 + 12i + 9). The index in is_prime
            # is (2i^2 + 6i + 3) because is_prime[i] represents 2i + 3

            # note that we need to use long for j because p^2 might overflow
            for j in range(2 * i**2 + 6 * i + 3, size, p):
                is_prime[j] = False
    return primes

Мои вопросы:

1. как они придумали формулу для размера
2. они говорят is_prime[i] represents (2i + 3) is prime or not. Я не могу понять, почему 2i + 3.
3. как они получили p = i * 2 + 3
4. что означает следующее Sieving from p^2, where p^2 = (4i^2 + 12i + 9). The index in is_prime is (2i^2 + 6i + 3) because is_prime[i] represents 2i + 3
5. почему диапазон j начинается с 2 * i**2 + 6 * i + 3

Большинство чисел кажутся мне довольно случайными

Answer 1

Здесь есть два ключевых трюка, которые выполняются одновременно. Это, я полагаю, главная причина вашего замешательства. Первый - это математический факт о прогрессии алгоритма сита. (то есть, начиная с p<sup>2</sup>). Другой прием - использовать меньше места, не сохраняя данные is_prime для четных чисел)

Давайте начнем с первых двух вопросов. Отображение (2 * i + 3), используемое в is_prime[i], похоже, является пространственной оптимизацией, чтобы уменьшить используемое пространство до половины. (т. е. четное число не представлено в списке is_prime). Сопоставление помогает перебирать только список нечетных чисел, начиная с 3 до size. Если вы на самом деле замените переменную i в (2i + 3) начальным значением size, вы увидите, что в итоге вы получите n. (или n-1, в зависимости от того, является ли n четным или нечетным)

Ваш третий вопрос является относительно более простым. Во внешнем l oop, i перебирает пространство нечетных целых чисел до n. Поскольку в is_prime есть отображение (2i + 3), этому значению присваивается p. С этого момента, p представляет фактическое простое значение, которое должно использоваться во внутреннем l oop.

Комментарий в вашем четвертом вопросе просто далее объясняет математическую идею начать итерацию с p<sup>2</sup>. Поскольку l oop составляет i, чтобы быть частью отображения (к фактическим значениям), p<sup>2</sup> далее выражается через эту переменную i. Я думаю, что комментарий пытается express использовать 2 * i**2 + 6 * i + 3 для инициализации диапазона j, но совершенно неясно.

Чтобы ответить на ваш последний вопрос, мы должны рассмотреть, что на самом деле представляет j , j представляет пространство нечетных чисел для обновления. Аналогично l oop для i, j повторяется не по фактическим значениям, а по нечетным числам . Начальное значение j равно 2 * i**2 + 6 * i + 3, потому что когда вы заменяете это значение переменной i в (2*i + 3) (т. Е. Отображением пространства нечетных чисел в набор фактических значений), вы получаете 4 * i**2 + 12 * i + 9, то есть p<sup>2</sup>.

Внутренний l oop в основном присваивает is_prime[j]=False всем ячейкам, которые представляют кратные фактического простого значения p, начиная с единицы, представляющей значение p<sup>2</sup>.

Answer 2

Наивная реализация сита будет иметь массив is_prime, который представляет все n числа, которые мы хотим проверить. Таким образом, его размер будет n. Затем для каждого p мы начинаем с 2*p и помечаем его как «не простое», затем go до 3*p, 4*p, 5*p и т. Д. c, отмечая каждый как «не простое» ». Так, например, когда p = 2, мы отмечаем 4, 6, 8, 10, 12 и т.д. c как «не простые». Затем, когда p = 3, мы отмечаем 6, 9, 12, 15 как «не простые».

Я предлагаю вам реализовать этот алгоритм самостоятельно, чтобы понять, как он работает, прежде чем переходить к реализации. Код, который вы просматриваете, использует некоторые приемы, чтобы уменьшить объем работы. Но чтобы понять эти уловки, вам нужно понять базовый алгоритм.

как они пришли с формулой для размера

Это происходит из решения формулы n = i * 2 + 3 для i, где n - наибольшее число, которое мы проверим на простоту. Он дает верхнюю границу значения i для всех чисел, которые мы хотим проверить.

как они получили p = i * 2 + 3

Это позволяет нам проверять только нечетные числа, начиная с 3. Обратите внимание, что четные числа не простые, поэтому мы можем легко пропустить их с помощью этой формулы.

что делает следующее среднее сито от р ^ 2, где р ^ 2 = (4i ^ 2 + 12i + 9). Индекс в is_prime равен (2i ^ 2 + 6i + 3), потому что is_prime [i] представляет 2i + 3

Обратите внимание, что в нашем простом алгоритме мы отметили 6 и 12 как «не простые» дважды , Мы явно делаем дополнительную работу здесь. Мы можем избежать этой дополнительной работы, осознав, что для p мы уже пометили все составные числа меньше p^2 как «не простые», когда мы определили каждое простое число меньше p.

Итак, мы начинать нужно только с p^2 вместо p. Теперь для p = 2 мы отмечаем 4, 6, 8, 10, 12 и т. Д. c, как и раньше. Но затем для p = 3 мы отмечаем 9, 12, 15, 18 и т. Д. c, избегая двойной работы с маркировкой 6 как «не простой». Для этих двух примеров избегаемая двойная маркировка довольно мала, но по мере увеличения p эта техника приводит к значительному увеличению производительности.

Что касается формулы p^2 = (4i^2 + 12i + 9), вы можете выведите это из того, что мы называем методом FOIL при умножении (2*i+3)*(2*i+3). Для вашего кода это на самом деле не имеет значения, потому что если вы делаете p = 2*i + 3, то вы можете вычислить p*p напрямую, не беспокоясь о базовых алгебраических c манипуляциях.

почему диапазон j начинается с 2 * i ** 2 + 6 * i + 3

У нас есть p^2 = (4i^2 + 12i + 9), и нам нужно найти индекс j в is_prime, где p^2 = j * 2 + 3. Мы устанавливаем их равными и решаем для j.