Не могу понять этот алгоритм простого генератора в моем учебнике

Я изучаю Elements of Programming Interviews, и я застрял в проблеме. Речь идет о написании функции С++ для нахождения всех простых чисел от 1 до n для заданного n.

vector<int> generate_primes_from_1_to_n(const int &n) {
    int size = floor(0.5 * (n - 3)) + 1;
    // is_prime[i] represents (2i+3) is prime or not

    vector<int> primes; // stores the primes from 1 to n

    primes.push_back(2);
    vector<bool> is_prime(size, true);

    for(long i = 0; i < size; ++i) {
       if(is_prime[i]) {
           int p = (i << 1) + 3;
           primes.push_back(p);
           // sieving from p^2, whose index is 2i^2 + 6i + 3
           for (long j = ((i * i) << 1) + 6 * i + 3; j < size; j += p) {
               is_prime[j] = false;
           }
       }
    }
}

В частности, я не могу понять прокомментированное "просеивание" из p ^ 2, индекс которого составляет 2i ^ 2 + 6i + 3 '. Для других частей я могу понять грубое представление о том, как они работают, но я не знаю, откуда взялось это "2i ^ 2 + 6i + 3", что он делает и как это и связанные с ним части коды работают.

Может ли кто-нибудь объяснить этот код лучше? Спасибо.

Я получаю этот вывод (+ 'cout, чтобы понять его лучше)

./a.out 100
size is: 49
for i = 0 is_prime[i] is 1
pushing back p of size 3
((i * i) << 1) + 6 * i + 3 for i of 0 is 3
((i * i) << 1) + 6 * i + 3 for i of 0 is 6
((i * i) << 1) + 6 * i + 3 for i of 0 is 9
((i * i) << 1) + 6 * i + 3 for i of 0 is 12
((i * i) << 1) + 6 * i + 3 for i of 0 is 15
((i * i) << 1) + 6 * i + 3 for i of 0 is 18
((i * i) << 1) + 6 * i + 3 for i of 0 is 21
((i * i) << 1) + 6 * i + 3 for i of 0 is 24
((i * i) << 1) + 6 * i + 3 for i of 0 is 27
((i * i) << 1) + 6 * i + 3 for i of 0 is 30
((i * i) << 1) + 6 * i + 3 for i of 0 is 33
((i * i) << 1) + 6 * i + 3 for i of 0 is 36
((i * i) << 1) + 6 * i + 3 for i of 0 is 39
((i * i) << 1) + 6 * i + 3 for i of 0 is 42
((i * i) << 1) + 6 * i + 3 for i of 0 is 45
((i * i) << 1) + 6 * i + 3 for i of 0 is 48
for i = 1 is_prime[i] is 1
pushing back p of size 5
((i * i) << 1) + 6 * i + 3 for i of 1 is 11
((i * i) << 1) + 6 * i + 3 for i of 1 is 16
((i * i) << 1) + 6 * i + 3 for i of 1 is 21
((i * i) << 1) + 6 * i + 3 for i of 1 is 26
((i * i) << 1) + 6 * i + 3 for i of 1 is 31
((i * i) << 1) + 6 * i + 3 for i of 1 is 36
((i * i) << 1) + 6 * i + 3 for i of 1 is 41
((i * i) << 1) + 6 * i + 3 for i of 1 is 46
for i = 2 is_prime[i] is 1
pushing back p of size 7
((i * i) << 1) + 6 * i + 3 for i of 2 is 23
((i * i) << 1) + 6 * i + 3 for i of 2 is 30
((i * i) << 1) + 6 * i + 3 for i of 2 is 37
((i * i) << 1) + 6 * i + 3 for i of 2 is 44
for i = 3 is_prime[i] is 0
for i = 4 is_prime[i] is 1
pushing back p of size 11
for i = 5 is_prime[i] is 1
pushing back p of size 13
for i = 6 is_prime[i] is 0
for i = 7 is_prime[i] is 1
pushing back p of size 17
for i = 8 is_prime[i] is 1
pushing back p of size 19
for i = 9 is_prime[i] is 0
for i = 10 is_prime[i] is 1
pushing back p of size 23
for i = 11 is_prime[i] is 0
for i = 12 is_prime[i] is 0
for i = 13 is_prime[i] is 1
pushing back p of size 29
for i = 14 is_prime[i] is 1
pushing back p of size 31
for i = 15 is_prime[i] is 0
for i = 16 is_prime[i] is 0
for i = 17 is_prime[i] is 1
pushing back p of size 37
for i = 18 is_prime[i] is 0
for i = 19 is_prime[i] is 1
pushing back p of size 41
for i = 20 is_prime[i] is 1
pushing back p of size 43
for i = 21 is_prime[i] is 0
for i = 22 is_prime[i] is 1
pushing back p of size 47
for i = 23 is_prime[i] is 0
for i = 24 is_prime[i] is 0
for i = 25 is_prime[i] is 1
pushing back p of size 53
for i = 26 is_prime[i] is 0
for i = 27 is_prime[i] is 0
for i = 28 is_prime[i] is 1
pushing back p of size 59
for i = 29 is_prime[i] is 1
pushing back p of size 61
for i = 30 is_prime[i] is 0
for i = 31 is_prime[i] is 0
for i = 32 is_prime[i] is 1
pushing back p of size 67
for i = 33 is_prime[i] is 0
for i = 34 is_prime[i] is 1
pushing back p of size 71
for i = 35 is_prime[i] is 1
pushing back p of size 73
for i = 36 is_prime[i] is 0
for i = 37 is_prime[i] is 0
for i = 38 is_prime[i] is 1
pushing back p of size 79
for i = 39 is_prime[i] is 0
for i = 40 is_prime[i] is 1
pushing back p of size 83
for i = 41 is_prime[i] is 0
for i = 42 is_prime[i] is 0
for i = 43 is_prime[i] is 1
pushing back p of size 89
for i = 44 is_prime[i] is 0
for i = 45 is_prime[i] is 0
for i = 46 is_prime[i] is 0
for i = 47 is_prime[i] is 1
pushing back p of size 97
for i = 48 is_prime[i] is 0

Это тоже не имеет смысла.

Например, почему при p = 5 он начинает удалять его из 11, а не 5 ^ 2 = 25, в строках ниже? отталкивание назад p размера 5 ((i * i) < 1) + 6 * я + 3 для я из 1 составляет 11

Кроме того, не 11 простое? Это действительно сбивает с толку. Пожалуйста, помогите мне. Спасибо.

Ответ 1

Алгоритм

Алгоритм, используемый вашим основным генераторным кодом, называется "Решетка Эратосфена". В общем, он создает список чисел и выполняет итерацию по списку. Все умножения текущего числа удаляются из списка, а остальные числа - простые.

Например, рассмотрим [2,3,4,5,6,7,8,9,10,11,12,13,14,15]. Мы сталкиваемся с 2, поэтому мы удаляем все четные числа из списка:

[2,3,5,7,9,11,13,15]

То же самое для 3:

[2,3,5,7,11,13]

5, 7, 11 и 13 не имеют умножений в списке, поэтому мы ничего не удаляем и сохраняем список простых чисел.

Визуальный пример

В этом примере (любезно предоставлено Википедии) все умножения на 2, 3 и 5 были удалены из списка - умножения на 2 были окрашены в розовый цвет, умножение на 3 было окрашено в зеленый цвет и умножено на 5 в темно-синем. 7 будет повторен следующим образом, поэтому он будет выделен. Темные цветные числа являются первичными, светлые номера не являются первичными, а серые цифры еще не достигнуты.

Оптимизация в коде

Как уже упоминалось @BenJackson, ваш код оптимизирован дважды:

Во-первых, он хранит только нечетные числа, начиная с 3, потому что мы знаем, что четные числа не являются первыми (кроме 2).
Во-вторых, для числа p он только начинает просеиваться из p². Это верно, потому что если n<p, то n*p уже просеивалось, когда просеивались умножения n.

Вот почему критический комментарий:

// sieving from p^2, whose index is 2i^2 + 6i + 3

Предположим, что наш алгоритм достиг второго элемента в векторе, поэтому i=2. Число, о котором идет речь, равно 5, так как индекс i обозначает число 2i+3 (первая оптимизация).

Мы должны просеять все умножения 5 из 25 и далее. Индекс, который представляет 25, равен 11, потому что 25=2*11+3. После ваших распечаток он удаляет индексы 11, 16, 21, 26, ..., которые соответствуют номерам 25, 35, 45, 55, .. - всем нечетным умножениям 5, которые мы хотели бы удалить.

Подробнее об этом можно узнать в Wikipedia или Wolfram MathWorld, и здесь есть приятная демонстрация онлайн-объявлений javascript.

Ответ 2

В таблице простых чисел хранятся нечетные значения, начиная с 3 (очевидно, четные значения не могут быть первыми). Отношение задается в строке int p = (i << 1) + 3 или p = 2i + 3. Теперь разрешите это для i, получив i = (p - 3)/2. Теперь, что i соответствует p^2? Подключите (2i+3)^2 к этой второй формуле и упростите. Теперь у вас есть i для p^2 в терминах i для p.

Пример: пусть говорят i=1, поэтому запись is_prime[i] является тестом простого p=2i+3 или p=5. Так что да, это просто. Теперь сивуэт (объясненный в другом месте) хочет начать отмечать простые числа в 25. Ему нужно знать, что i соответствует 25. Теперь вы можете просто вычислить p*p, а затем вставить это в i=(p-3)/2 и получить j=11, Код пропустил эти промежуточные шаги (как я показал выше), чтобы вычислить j=2i^2+6i+3 и получить j=11 напрямую.

Ответ 3

Линии, подобные этим:

vector<int> generate_primes_from_1_to_n(const int &n) {
    int size = floor(0.5 * (n - 3)) + 1;

...

for(long i = 0; i < size; ++i) {
   if(is_prime[i]) {
       int p = (i << 1) + 3;

являются "взломом", так что потенциальные простые числа 3, 5, 7 и т.д. можно повторить путем итерации 0, 1, 2, 3 в i и используя p для соответствующих возможных простых чисел 3, 5, 7, 9 и т.д.

Это основное первичное сито, отличное от этого.

Ответ 4

Как отмечали другие, я сопоставляет местоположения массивов, а p отображает числа, которые представляют эти местоположения в массиве, в соответствии с формулой p = 2 я + 1. Возможно, будет легче подумать, если вы сохраните я и p явно в программа:

function primes(n)
    m := floor((n-1)/2)
    sieve := makeArray(0..m-1, True)
    i := 0; p := 3; ps := [2]
    while p * p <= n
        if sieve[i]
            append p to ps
            j := (p*p - 3) / 2
            while j < m
                sieve[j] := False
                j := j + p
        i := i + 1; p := p + 2
    while i < m
        if sieve[i]
            append p to ps
        i := i + 1; p := p + 2
    return ps

Странная формула для j в исходном коде формируется с помощью приведенной выше формулы для j и переписывания в терминах я вместо p.

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