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

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

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

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

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

Алгоритмы определения простых чисел - student2.ru 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, начиная с Алгоритмы определения простых чисел - student2.ru .

Алгоритмы определения простых чисел - student2.ru 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, начиная с Алгоритмы определения простых чисел - student2.ru .

Алгоритмы определения простых чисел - student2.ru 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, начиная с Алгоритмы определения простых чисел - student2.ru .

Алгоритмы определения простых чисел - student2.ru 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

Были выполнены все зачеркивания чисел, кратных простому числу Алгоритмы определения простых чисел - student2.ru , для которых Алгоритмы определения простых чисел - student2.ru . Незачёркнутыми оказались простые числа:

Алгоритмы определения простых чисел - student2.ru 3 5 7 11 13 17 19 23 29

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

Наши рекомендации