Метка: решето эратосфена

Очень интересными с математической (и не только) точки зрения считаются простые числа. Для начала сформулируем несколько определений для дальнейшей работы.

Определение. Простое число — это натуральное число больше единицы и которое делится нацело только на единицу и на само себя. Таким образом, $p$ считается простым, если

Определение. Натуральное число не являющиеся простым и больше $1$ называется составным.

Примеры

1. $3, 5, 7, 23$ — простые числа, что можно с легкостью проверить мысленно перебрав возможные делители для этих чисел. $177539$ — тоже простое число, однако проверить это устным перебором делителей будет значительно сложнее.
2. Любое четное число кроме $2$ — составное, так как имеет как минимум один делитель помимо $1$ и самого себя — $2$.

Леммы

Сформулируем и докажем несколько лемм. Далее, если это потребуется, будем упоминать их как лемму и её номер в списке. Лемма (2), к примеру.

1. Лемма. Пусть $p$ и является наименьшим делителем (не считая $1$) $n \in N, n > 1$. Тогда $p$ — простое число.
   
   Спойлер

   Докажем от обратного. Предположим что $p$, наименьший делитель для $n$ из условия, составное число. В таком случае, его можно представить как $p=p_{1}p_{2}$. Отсюда $n=pb$ можно представить как $n=p_{1}p_{2}b$, где $p_{1}, p_{2} < p$. Если $n \vdots p$, то оно делится и на $p_{1}, p_{2}$. А так как они оба меньше $p$, то $p$ не может быть наименьшим делителем $n$. Таким образом, составное число не может быть наименьшим делителем числа, так как его всегда можно разложить на множители, которые в свою очередь тоже будут делителями $n$.

   [свернуть]
2. Лемма. Пусть $p$ — наименьший (не считая $1$) натуральный делитель составного числа $n$. Тогда $p\leqslant \sqrt{n}$.
   
   Спойлер

   Пусть, по условию леммы, $p$ — наименьший отличный от нуля делитель $n$. Тогда $n = pb$, где $b\in N$ и $b\mid n$. Очевидно, что в таком случае $p \leqslant b < n$ и отсюда $p^{2} \leqslant n$, что доказывает неравенство данное в условии.

   [свернуть]

Решето Эратосфена

Алгоритм. Способ нахождения простых чисел до определенного $n$. Метод подразумевает фильтрацию чисел до $n$, отсеивая составные числа. Является псевдополиномиальным алгоритмом. Алгоритм заключается в следующем:

1. Требуется выписать все числа от $2$ до $n$.
2. Изначально $p=2$.
3. Далее вычеркнем все числа представимые в виде $2p, 3p, 4p, \ldots$ до $n$.
4. Присвоим $p$ следующее не вычеркнутое число. Будем повторять $3$ и $4$ шаги до тех пор, пока $p \leqslant \sqrt{n}$ (по лемме (2)).
5. Таким образом, все составные числа будут вычеркнуты и останутся только простые.

Пример