Как сделать решето эратосфена

Обновлено: 04.07.2024

Решето Эратосфена — алгоритм нахождения всех простых чисел до некоторого целого числа n, который приписывают древнегреческому математику Эратосфену Киренскому. Как и во многих случаях, здесь название алгоритма говорит о принципе его работы, то есть решето подразумевает фильтрацию, в данном случае фильтрацию всех чисел за исключением простых. По мере прохождения списка нужные числа остаются, а ненужные (они называются составными) исключаются.

История

Алгоритм

Для нахождения всех простых чисел не больше заданного числа n, следуя методу Эратосфена, нужно выполнить следующие шаги:

Теперь все незачёркнутые числа в списке — это все простые числа от 2 до n.

На практике, алгоритм можно улучшить следующим образом. На шаге № 3 числа можно зачеркивать начиная сразу с числа p2, потому что все меньшие числа, кратные p, обязательно имеют простой делитель меньше p, а они уже зачеркнуты к этому времени. И, соответственно, останавливать алгоритм можно, когда p2 станет больше, чем n. Также, все простые числа (кроме 2) — нечётные числа, и поэтому для них можно считать шагами по 2p, начиная с p2.

Пример для n = 30

Запишем натуральные числа, начиная от 2, до 30 в ряд:

2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30

Первое число в списке, 2 — простое. Пройдём по ряду чисел, зачёркивая все числа, кратные 2 (то есть, каждое второе, начиная с 22 = 4):

2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30

Следующее незачеркнутое число, 3 — простое. Пройдём по ряду чисел, зачёркивая все числа, кратные 3 (то есть, каждое третье, начиная с 32 = 9):

Следующее незачеркнутое число, 5 — простое. Пройдём по ряду чисел, зачёркивая все числа, кратные 5 (то есть, каждое пятое, начиная с 52 = 25):

Следующее незачеркнутое число — 7. Его квадрат, 49 — больше 30, поэтому на этом работа завершена. Все составные числа уже зачеркнуты:

2 3 5 7 11 13 17 19 23 29

Псевдокод

Оптимизированная реализация (начинающаяся с квадратов) на псевдокоде:

Сложность алгоритма

Сложность алгоритма составляет O ( n log ⁡ ( log ⁡ n ) ) операций при составлении таблицы простых чисел до n .

Доказательство сложности

При выбранном n ∈ N > для каждого простого p ∈ P : p ≤ n colon pleq n> будет выполняться внутренний цикл, который совершит n p

>> действий. Сложность алгоритма можно получить из оценки следующей величины:

∑ p ∈ P : p ≤ n n p = n ⋅ ∑ p ∈ P : p ≤ n 1 p colon pleq n>

>=ncdot sum limits _ colon pleq n>

Так как количество простых чисел, меньших либо равных n , оценивается как n ln ⁡ n >> , и, как следствие, k -е простое число примерно равно k ln ⁡ k , то сумму можно преобразовать:

Здесь из суммы выделено слагаемое для первого простого числа, чтобы избежать деления на нуль. Данную сумму можно оценить интегралом

1 2 + ∑ k = 2 n ln ⁡ n 1 k ln ⁡ k ≈ ∫ 2 n ln ⁡ n 1 k ln ⁡ k d k = ln ⁡ ln ⁡ k | 2 n ln ⁡ n = ln ⁡ ln ⁡ n ln ⁡ n − ln ⁡ ln ⁡ 2 = ln ⁡ ( ln ⁡ n − ln ⁡ ln ⁡ n ) − ln ⁡ ln ⁡ 2 ≈ ln ⁡ ln ⁡ n >+sum _^>>approx int limits _^>>,dk=ln ln k_^>=ln ln >-ln ln 2=ln(ln n-ln ln n)-ln ln 2approx ln ln n>

В итоге получается для изначальной суммы:

∑ p ∈ P : p ≤ n n p ≈ n ln ⁡ ln ⁡ n + o ( n ) colon pleq n>

>approx nln ln n+o(n)>

Модификации метода

Неограниченный, постепенный вариант

В этом варианте простые числа вычисляются последовательно, без ограничения сверху, как числа находящиеся в промежутках между составными числами, которые вычисляются для каждого простого числа p, начиная с его квадрата, с шагом в p (или для нечетных простых чисел 2p). Может быть представлен символически в парадигме потоков данных как

primes = [2..] [[p², p²+p..] for p in primes]

используя нотацию абстракции списков, где обозначает разницу между арифметическими прогрессиями.

Первое простое число 2 (среди возрастающих положительных целых чисел) заранее известно, поэтому в этом самореферентном определении нет порочного круга.

Псевдокод поэтапного отсеивания, в неэффективной, для простоты, реализации (ср. с нижеследующими вариантами):

primes = sieve [2..] where sieve [p, . xs] = [p, . sieve (xs [p², p²+p..])]

Перебор делителей

Решето Эратосфена часто путают с алгоритмами, которые поэтапно отфильтровывают составные числа, тестируя каждое из чисел-кандидатов на делимость используя по одному простому числу на каждом этапе.

Широко известный функциональный код Дэвида Тёрнера 1975 г. часто принимают за решето Эратосфена, но на самом деле это неоптимальный вариант с перебором делителей (в оптимальном варианте не используются делители, большие квадратного корня тестируемого числа). В псевдокоде,

primes = sieve [2..] where sieve [p, . xs] = [p, . sieve [x in xs if x%p > 0]]

Сегментированное решето

Как замечает Соренсон, главной проблемой реализации решета Эратосфена на вычислительных машинах является не количество выполняемых операций, а требования по объёму занимаемой памяти (впрочем, его замечание относится к неактуальному сейчас компьютеру DEC VAXstation 3200, выпущенному в 1989 году). При больших значениях n, диапазон простых чисел может превысить доступную память; хуже того, даже при сравнительно небольших n использование кэша памяти далеко от оптимального, так как алгоритм, проходя по всему массиву, нарушает принцип локализованности ссылок.

Для решения представленной проблемы используется сегментированное решето, в котором за итерацию просеивается только часть диапазона простых чисел. Данный метод известен с 1970-х годов и работает следующим образом:

Если число Δ выбрано равным √n, то сложность алгоритма по памяти оценивается как O(√n), а операционная сложность остаётся такой же, что и у обычного решета Эратосфена.

Для случаев, когда n настолько велико, что все просеиваемые простые числа меньшие √n не могут уместиться в памяти, как того требует алгоритм сегментированного сита, используют более медленные, но с гораздо меньшими требованиями по памяти алгоритмы, например решето Соренсона.

Решето Эйлера

Доказательство тождества Эйлера для дзета-функции Римана содержит механизм отсеивания составных чисел подобный решету Эратосфена, но так, что каждое составное число удаляется из списка только один раз. Схожее решето описано в Gries & Misra 1978 г. как решето с линейным временем работы (см. ниже).

Составляется исходный список начиная с числа 2. На каждом этапе алгоритма первый номер в списке берется как следующее простое число, результаты произведения которого на каждое число в списке помечаются для последующего удаления. После этого из списка убирают первое число и все помеченные числа, и процесс повторяется вновь:

[2] (3) 5 7 9 11 13 15 17 19 21 23 25 27 29 31 33 35 37 39 41 43 45 47 49 51 53 55 57 59 61 63 65 67 69 71 73 75 77 79 . [3] (5) 7 11 13 17 19 23 25 29 31 35 37 41 43 47 49 53 55 59 61 65 67 71 73 77 79 . [4] (7) 11 13 17 19 23 29 31 37 41 43 47 49 53 59 61 67 71 73 77 79 . [5] (11) 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 . [. ]

Здесь показан пример начиная с нечетных чисел, после первого этапа алгоритма. Таким образом, после k-го этапа рабочий список содержит только числа взаимно простые с первыми k простыми числами (то есть числа не кратные ни одному из первых k простых чисел), и начинается с (k+1)-го простого числа. Все числа в списке, меньшие квадрата его первого числа, являются простыми.

primes = sieve [2..] where sieve [p, . xs] = [p, . sieve (xs [p², . [p*x for x in xs]])]

Решето только по нечётным числам

Поскольку все чётные числа, кроме 2, — составные, то можно вообще не обрабатывать никак чётные числа, а оперировать только нечётными числами. Во-первых, это позволит вдвое сократить объём требуемой памяти. Во-вторых, это уменьшит количество выполняемых алгоритмом операций (примерно вдвое).

Это можно обобщить на числа взаимно простые не только с 2 (то есть нечетные числа), но и с 3, 5, и т. д.

Уменьшение объёма потребляемой памяти

Алгоритм Эратосфена фактически оперирует с n битами памяти. Следовательно, можно существенно сэкономить потребление памяти, храня n переменных булевского типа не как n байт, а как n бит, то есть n / 8 байт памяти.

Решето Эратосфена с линейным временем работы

Этот алгоритм обнаруживает для каждого числа i в отрезке [2. n] его минимальный простой делитель lp[i] (lp от англ. least prime).

Также поддерживается список всех простых чисел — массив pr[], поначалу пустой. В ходе работы алгоритма этот массив будет постепенно заполняться.

Изначально все величины lp[i] заполним нулями.

Дальше следует перебрать текущее число i от 2 до n. Здесь может быть два случая:

lp[i] = 0: это означает, что число i — простое, так как для него так и не обнаружилось других делителей.

Следовательно, надо присвоить lp[i] = i и добавить i в конец списка pr[].

lp[i] ≠ 0: это означает, что текущее число i — составное, и его минимальным простым делителем является lp[i].

В обоих случаях дальше начинается процесс расстановки значений в массиве lp[i]: следует брать числа, кратные i, и обновлять у них значение lp[]. Однако основная цель — научиться делать это таким образом, чтобы в итоге у каждого числа значение lp[] было бы установлено не более одного раза.

Утверждается, что для этого можно поступить таким образом. Рассматриваются числа вида x = p ⋅ i, где p последовательно равно всем простым числам не превосходящим lp[i] (как раз для этого понадобилось хранить список всех простых чисел).

У всех чисел такого вида проставим новое значение lp[x] — оно должно быть равно p.

Псевдокод

Сложность алгоритма на практике

Решето Эратосфена является популярным способом оценки производительности компьютера. Как видно из вышеизложенного доказательства сложности алгоритма, избавившись от константы и слагаемого очень близкого к нулю (ln (ln n - ln ln n) - ln ln 2 ≈ ln ln n), временная сложность вычисления всех простых чисел меньше n аппроксимируется следующим соотношением O(n ln ln n). Однако алгоритм имеет экспоненциальную временную сложность в отношении размера входных данных, что делает его псевдополиномиальным алгоритмом. Памяти же для базового алгоритма требуется O(n).

Сегментированная версия имеет ту же операционную сложность O(n ln ln n),. что и несегментированная версия, но уменьшает потребность в используемой памяти до размера сегмента (размер сегмента значительно меньше размера всего массива простых чисел), который равен O(√n/ln n). Также существует очень редко встречающееся на практике оптимизированное сегментированное решето Эратосфена. Оно строится за O(n) операций и занимает O(√n ln ln n/ln n) бит в памяти.

На практике оказывается, что оценка ln ln n не очень точна даже для максимальных практических диапазонов таких как 1016. Ознакомившись с вышеописанным доказательством сложности, нетрудно понять откуда взялась неточность оценки. Расхождение с оценкой можно объяснить следующим образом: в пределах данного практического диапазона просеивания существенное влияние оказывают постоянные смещения. Таким образом очень медленно растущий член ln ln n не становится достаточно большим, чтобы константами можно было справедливо пренебречь, до тех пор пока n не приблизится к бесконечности, что естественно выходит за границы любого прикладного диапазона просеивания. Данный факт показывает, что для актуальных на сегодняшний день входных данных производительность решета Эратосфена намного лучше, чем следовало ожидать, используя только асимптотические оценки временной сложности.

Популярным способом ускорения алгоритмов, работающих с большими массивами чисел, является разного рода факторизация. Применение методов факторизации даёт значительное уменьшение операционной сложности за счёт оптимизации входного массива данных. Для индексных алгоритмов часто используют кольцевую факторизацию. Рассматриваемые в данной статье алгоритмы нахождения всех простых чисел до заданного n подобные решету Эратосфена относятся к индексным, что позволяет применять к ним метод кольцевой факторизации.

Несмотря на теоретическое ускорение, получаемое с помощью кольцевой факторизации, на практике существуют факторы, которые не учитываются при расчётах, но способны оказать существенное влияние на поведение алгоритма, что в результате может не дать ожидаемого прироста в быстродействии. Рассмотрим наиболее существенные из них:

Умножение и деление. При аналитических расчётах предполагается, что скорость выполнения арифметических операций равноценна. Но на самом деле это не так, и умножение, и деление выполняются гораздо медленнее, чем сложение и вычитание. Таким образом данный фактор никак не влияет на решето Эратосфена, поскольку оно использует только сложение и вычитание, но является весьма существенным для решета Питчарда (один из результатов усложнения вычислений упомянутого выше).
Оптимизация компилятора. Компилятор оптимизирует на стадии компиляции все программы для более корректного исполнения машиной. Но часто бывает очень сложно сказать, какой вклад даёт данная оптимизация, и будет ли этот вклад одинаковым для двух различных алгоритмов.
Кэш. Процессор использует кэш, чтобы ускорить извлечение инструкций и данных из памяти. Наличие кэша приводит к тому, что программы, использующие локализованные ссылки, будут работать быстрее. Но алгоритмы просеивания простых чисел, которые используют факторизацию высокой степени, часто генерируют случайные ссылки в память, что снижает их производительность.

Для наглядности представления вклада факторизации в производительность алгоритмов просеивания ниже приведены две таблицы. В таблицах приведены результаты измерения реального времени исполнения решета Эратосфена и решета Питчарда в секундах для разных диапазонов n и разных степеней кольцевой факторизации. Ei и Pi обозначения для решета Эратосфена и Питчарда соответственно, где индекс i означает степень кольцевой факторизации. Стоит отметить, что E0 и P0 означают отсутствие факторизации.

Из таблицы видно, что лучшую производительность имеет решето Эратосфена со средней степенью факторизации E2. Данный факт можно объяснить влиянием кэш-фактора, рассмотренного выше, на алгоритмы с высокой степенью факторизации.

В заключение стоит отметить, что с увеличением n соотношение времен становится всё больше в пользу решета Эратосфена, а на диапазоне n = 5000000 оно стабильно быстрее при любых факторизациях. Данный факт ещё раз подтверждает проигрыш в быстродействии решета Питчарда из-за сложных вычислений.

Решето Эратосфена — алгоритм нахождения всех простых чисел от $1$ до $n$ за $O(n \cdot \log<\log>)$ или за $O(n)$ в зависимости от реализации.

Содержание

Запишем все числа от $2$ до $n$ ($1$ - не простое). Затем будем вычеркивать:

числа, кратные $2$, кроме самого числа $2$
числа, кратные $3$, кроме самого числа $3$
числа, кратные $4$, не трогаем, так как они, как и само число $4$, были вычеркнуты ранее
числа, кратные $5$, кроме самого числа $5$

Простейшая реализация данного алгоритма будет выглядеть примерно так:

Функция помечает сначала все числа как простые, вычеркивает $0$ и $1$ (они не простые), а затем для каждого числа $i$ от $2$ до $n$, если оно простое, вычеркивает все числа, кратные ему (кроме него самого).

Если нет жестких требований по памяти, лучше использовать vector , так как vector размера $n$ упаковывается компьютером в $\lceil>\rceil$ байт, и последующие обращения к элементам получаются долгими.
Нетрудно понять, что если $x$ составное, то оно будет вычеркнуто его минимальным простым делителем. В функции выше в случае, если $i$ простое, мы вычеркивали числа, кратные $i$, начиная от $2 \cdot i$. Теперь мы можем вычеркивать числа, начиная с $i^2$, так как все меньшие кратные $i$ числа были вычеркнуты ранее.

Итоговая реализация требует совсем мало изменений и остается читателю в качестве упражнения.

Для начала несложно показать, что время работы хотя бы не хуже $O(n \cdot \log)$. Предположим, мы начинаем вычеркивать числа, кратные $i$, для каждого $i$ (вне зависимости от того, было ли $i$ вычеркнуто ранее как составное). Тогда время работы алгоритма будет: $$\sum_^<\frac> = \frac + \frac + . + \frac + \frac = O(n \cdot \log)$$ Тут мы использовали сумму гармонического ряда. Но вычеркивать мы начинаем только от простых чисел, поэтому асимптотика должна быть еще лучше. Для дальнейших рассуждений необходимы 2 факта:

простых чисел от $1$ до $n$ примерно $\frac<\ln>$
$k$-е простое число приблизительно равно $k \cdot \ln$

Будем упрощенно считать, что число является простым с вероятностью $\frac<\ln>$. Тогда время работы можно оценить как ALARM : оценка на коленке. Приблизим искомую сумму интегралом соответствующей функции. Перебираем числа $k$ от $1$ до $n/\ln n$, затем $k$-ое простое число примерно равно $k\ln k$, поэтому мы сделаем $\dfrac$ шагов по массиву. (Перейдем от последовательность $a_n$ к функции $f: f(n) = a_n$). \begin \sum \limits_^a_n = \sum \limits_^ \dfrac \\ \int_2^ \dfracdx = n\int_2^\dfrac <\ln x>= n\int_2^d(\ln \ln x) = O\left( n \ln \ln \dfrac<\ln n>\right) = O(n\ln \ln n) \\ \end

Тот факт, что мы можем пометить число как составное несколько раз (столько, сколько у него различных простых делителей), мешает нам добиться асимптотики $O(n)$. Придумаем, как помечать любое составное число ровно один раз.

Пусть $p[x]$ - минимальный простой делитель числа $x$. Заметим, что любое число $x$ можно представить в виде $x = p[x] * i$. При этом очевидно, что $p[x] \leq p[i]$. Ключевая идея состоит в том, чтобы перебирать $i$ и для каждого $i$ (вне зависимости от его простоты) перебирать только нужные множители (простые числа от 2 до $p[i]$).

Для этого нам понадобится поддерживать массив $p$ и дополнительно хранить все встретившиеся нам простые числа.

Алгоритм требует в 4 раза больше памяти, чем реализация с vector и в 32 раза больше памяти, чем реализация с vector . Линейное решето хоть и помогает нам добиться асимптотики $O(n)$, но проигрывает оптимизированному варианту решета Эратосфена за $O(n \cdot \log<\log>)$ из-за умножений и еще больших скачков по памяти.

После предподсчета вектора $p$ мы знаем, какие числа простые (все $x$, для которых $p[x] = x$), а для каждого составного числа знаем его минимальный простой делитель. Нетрудно понять, что вектор $p$ позволяет нам теперь находить факторизацию любого числа от $1$ до $n$ за количество его делителей: возьмем число $x$, поделим его на $p[x]$ (запомнив, что $p[x]$ входит в факторизацию) и будем повторять так до тех пор, пока $x \neq 1$. Так же, заведя еще один массив $h[x] = x / p[x]$, мы можем совсем избавиться от делений при факторизации числа.

Решето Эратосфена - достаточно эффективный алгоритм для нахождения всех простых чисел в отрезке от $1$ до $N$ за $O(N \log \log N)$.

Алгоритм достаточно тривиален: будем перебирать числа по возрастанию, начиная с $2$, зачёркивая все числа, кратные текущему. Например, при обработке числа $2$ будут зачёркнуты числа $4, 6, 8, \ldots$. Если мы обнаружили незачёркнутое число, это значит, что оно простое.

Визуализация работы решета Эратосфена:

Работу решета можно значительно ускорить, если начинать зачёркивать числа, кратные $p$, не с $2p$, а с $p^2$. Ведь числа $2p, 3p, 5p, \ldots$ уже были зачёркнуты при обработке чисел $2, 3, 5, \ldots$

Реализация

Сложность алгоритма. Гармонический ряд

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

\[1 + \frac + \frac + \ldots + \frac = \sum_^ \frac \approx \log(n)\]

Такую сумму называют “гармоническим рядом”, и она часто появляется в оценках сложности алгоритмов. Например, посмотрим на решето Эратосфена, в самой его наивной реализации: будем выполнять зачёркивающий цикл для каждого $x \in [2; n]$. То есть, для $x = 2$ мы проверим $\frac$ элементов (и часть из них зачеркнём), для $x = 3$ проверим $\frac$, и так далее, вплоть до $x = N$. Напомним, что сейчас мы рассматриваем гипотетическую, самую наивную версию алгоритма, так что представим, что мы выполняем зачёркивающий цикл даже для уже зачёркнутых элементов. Заметим, что общее число итераций зачёркивающего цикла можно оценить как

\[\frac + \frac + \ldots + \frac = N * (\sum_^ \frac) \approx N * (\log(N) - 1) = O(N \log N)\]

А значит сложность нашей гипотетической наивной версии алгоритма равна $O(N \log N)$. Возвращаясь в реальность, оптимальная версия отличается от гипотетической несколькими свойствами:

Зачёркивающий цикл выполняется только для простых $x \le N$, а не для всех.
Зачёркивающий цикл начинает выполнение с $x^2$, а не с $x$.

Используя эти свойства, можно доказать ещё более жёсткое ограничение для сложности: $O(N \log \log N) \le O(N \log N)$, но сделать это довольно непросто. К тому же, для олимпиадных задач такая точность не всегда оправдана: например для $N = 10^6$:

\[N \log N = 19.9 * 10^6 \\ N \log \log N = 4.3 * 10^6\]

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

Решето Эратосфена — алгоритм нахождения всех простых чисел до некоторого целого числа [math]n[/math] , который приписывают древнегреческому математику Эратосфену Киренскому.

Выписать подряд все целые числа от двух до n (2, 3, 4, …, n).
Пусть переменная p изначально равна двум — первому простому числу.
Вычеркнуть из списка все числа от 2p до n, делящиеся на p (то есть, числа 2p, 3p, 4p, …)
Найти первое не вычеркнутое число, большее чем p, и присвоить значению переменной p это число.
Повторять шаги 3 и 4 до тех пор, пока p не станет больше, чем n
Все не вычеркнутые числа в списке — простые числа.

На практике, алгоритм можно немного улучшить следующим образом. На шаге №3, числа можно вычеркивать, начиная сразу с числа [math]p^2[/math] , потому что все составные числа меньше его уже будут вычеркнуты к этому времени. И, соответственно, останавливать алгоритм можно, когда [math]p^2[/math] станет больше, чем [math]n[/math] .

Данный онлайн калькулятор строит решето Эратосфена до числа n, введенного пользователем. Выводятся также все простые числа до n. Для построения решето Эрастофена введите натуральное число до 5000 и нажмите на кнопку "Построить".

Предупреждение

Результат уже получен!

Решето Эратосфена − алгоритм

Греческий математик Эратосфен придумал метод отыскания простых чисел до определенного числа n. Записываем натуральные числа до n. Например:

Сначала вычеркиваем число 1, которая не является ни простым ни составным числом. Далее, начиная с числа 2 вычеркиваются все числа, больше 2 и кратные 2, т.е. 4, 6, 8, 10, 12:

1 , 2, 3, 4 , 5, 6 , 7, 8 , 9, 10 , 11, 12

Потом выбираем первое оставшиеся число после числа 2. Это 3. Начиная с 3 вычеркиваем все числа больше 3 и кратные числу 3. Это числа 6, 9, 12:

1 , 2, 3, 4 , 5, 6 , 7, 8 , 9 , 10 , 11, 12

Продолжая далее, мы видим, что нет больше чисел, подлежащих вычеркиванию. Таким образом, все простые числа до 12 − это числа 2, 3, 5, 7, 11. Заметим, что процедуру можно остановить начиная с позиции числа 7, т.к. кратное числу 7 (2*7=14) больше числа 12.

Ниже мы представим алгоритм простроения таблицы простых чисел до n с помощью решето Эрастофена. Обозначим через P массив n элементов. Изначально все элементы массива (кроме первого) будут равны 1. После выполнения программы элементы массива P с значениями 1 будут соответствовать порядковому номеру простого числа в ряде натуральных чисел. Далее с помощью этого массива легко построить множество простых чисел до n.

Алгоритм нахождения индексов простых чисел до n:

После выполнения алгоритма мы получим индексы простых натуральных чисел. Далее используя цикл строим таблицу простых чисел до числа n, т.е. берем те числа из натурального ряда, для которых соответствующие значения P_i=1.

Читайте также: