Теорема Вильсона

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

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

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

Выписать подряд все целые числа от двух до n (2, 3, 4, …, n).

Пусть переменная p изначально равна двум — первому простому числу.

Вычеркнуть из списка все числа от 2p до n, делящиеся на p (то есть, числа 2p, 3p, 4p, …)

Найти первое не вычеркнутое число, большее чем p, и присвоить значению переменной p это число.

Повторять шаги 3 и 4 до тех пор, пока p не станет больше, чем n

Все не вычеркнутые числа в списке — простые числа.

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

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

2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

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

2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

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

2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

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

Необходимо провести вычёркивания кратных для всех простых чисел p, для которых . В результате все составные числа будут вычеркнуты, а невычеркнутыми останутся все простые числа. Для n = 20 уже после вычёркивания кратных числу 3 все составные числа получаются вычеркнутыми.

Для любого P эквивалентны следующие условия:

1). P –простое;

2). (P-1)!=-1 (mod P)

Неэффективен из-за большой трудоемкости.