2021-11-09
114
Основная проблема решета Эратосфена состоит в том, что некоторые числа мы будем помечать как составные несколько раз — а именно столько раз, сколько у них различных простых делителей. Чтобы достичь линейного времени работы, нам нужно придумать способ, как рассматривать все составные числа ровно один раз.
Наша цель — посчитать для каждого числа i от в отрезке [2; n] его минимальный простой делитель lp[i]. Кроме того, нам потребуется хранить список всех найденных простых чисел — назовём его вектором pr[].
Изначально все величины lp[i] заполним нулями, что означает, что мы пока предполагаем все числа простыми. В ходе работы алгоритма этот массив будет постепенно заполняться.
Будем теперь перебирать текущее число i от 2 до n. У нас может быть два случая:
● lp[i] = 0 — это означает, что число i — простое, т. к. для него так и не обнаружилось других делителей, следовательно, надо присвоить lp[i] = i и добавить i в конец списка pr[].
● lp[i]!= 0 — это означает, что текущее число i — составное, и его минимальным простым делителем является lp[i].
В обоих случаях дальше начинается процесс расстановки значений в массиве lp[]: мы будем брать числа, кратные i, и обновлять у них значение lp[]. Однако наша цель — научиться делать это таким образом, чтобы в итоге у каждого числа значение lp[] было бы установлено не более одного раза.
Утверждается, что для этого можно поступить таким образом. Рассмотрим числа вида:
x_j = i * p_j, где последовательность p_j — это все простые, не превосходящие lp[i] (как раз для этого нам понадобилось хранить список всех простых чисел). У всех чисел такого вида проставим новое значение lp[x_j] — очевидно, оно будет равно p_j.
