Алгоритмы определения простых чисел

Небольшую коллекцию простых чисел можно подобрать используя «решето Эратосфена» (III век до н. э.). Для нахождения всех простых чисел не больше заданного числа n, следуя методу Эратосфена, нужно выполнить следующие шаги:

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

Есть и более современный способ определения простых чисел. Функциональный код Давида Тернера 1975 года с перебором делителей, который часто путают с решетом Эратосфена. Рассмотрим случай для .

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

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, начиная с .

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, начиная с .

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

Следующее незачеркнутое простое число 5. Вычеркнем из ряда все числа, кратные 5, начиная с .

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 5 7 11 13 17 19 23 29

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