Простые числа. Решето Эратосфена

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

Определение. Простое число — это натуральное число больше единицы и которое делится нацело только на единицу и на само себя. Таким образом, $p$ считается простым, если $$p \in N, p > 1, \forall a \in N, a \neq 1, a \neq p, p \mbox{ mod } a \neq 0 .$$

Определение. Натуральное число не являющиеся простым и больше $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. Таким образом, все составные числа будут вычеркнуты и останутся только простые.

Замечание

Если внимательно взглянуть на алгоритм, можно заметить что мы начинаем вычеркивать с $p^{2}$. Пусть $k \in N, k > 1$ и $k$ очередное простое (а значит не вычеркнутое) число в списке. А значит, что перед тем как $p=k$, мы вычеркнули (при условии что $k>2$) $2k$, ведь на первом шаге мы вычеркнули все делящиеся на $2$ числа. Если $k>3$, то и все делящиеся на $3$ числа были уже вычеркнуты. То есть $3k$ уже вычеркнуто. Таким образом, все составные числа имеющие нетривиальные делители до $k(k-1)$ включительно уже вычеркнуты, поэтому искать число чтобы вычеркнуть стоит начиная от $p^{2}$. Подробнее с модфикациями алгоритма можно ознакомится на википедии и e-max.

Пример

Найдем все простые числа до $20$ с помощью решета Эратосфена. Для начала выпишем все числа. $$2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20$$

Положим $p=2$ и уберем все числа от $p^{2}$ до $20$. Останется $$2,3,\phantom{4,} 5,\phantom{6,} 7,\phantom{8,} 9,\phantom{10,} 11, \phantom{12,} 13,\phantom{14,} 15,\phantom{16,} 17,\phantom{18,} 19 \phantom{,20}$$

Далее $p=3$, и мы снова убираем ненужные нам числа. $$2,3,\phantom{4,} 5,\phantom{6,} 7,\phantom{8,} \phantom{9,10,} 11, \phantom{12,} 13,\phantom{14, 15, 16,} 17,\phantom{18,} 19 \phantom{,20}$$

Брать следующее $p$ не смысла, так как это будет $5$, а $5^{2}>20$. Таким образом мы нашли все простые числа до $20$.

Тест на простые числа и решето Эратосфена

У вас есть возможность проверить то, как вы усвоили материал.

Литература

  1. Электронный конспект по алгебре. Автор Белозеров.Г.С.
  2. И.М.Виноградов. Основы теории чисел. 6-ое издание, 1952 год. стр.18-20.

Добавить комментарий

Ваш адрес email не будет опубликован. Обязательные поля помечены *