Лекции.Орг
 

Категории:


Теория отведений Эйнтховена: Сердце человека – это мощная мышца. При синхронном возбуждении волокон сердечной мышцы...


ОБНОВЛЕНИЕ ЗЕМЛИ: Прошло более трех лет с тех пор, как Совет Министров СССР и Центральный Комитет ВКП...


Универсальный восьмиосный полувагона: Передний упор отлит в одно целое с ударной розеткой. Концевая балка 2 сварная, коробчатого сечения. Она состоит из...

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



Небольшую коллекцию простых чисел можно подобрать используя «решето Эратосфена» (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 до тех пор, пока не станет больше, чем 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

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

 





Дата добавления: 2015-05-08; просмотров: 711 | Нарушение авторских прав


Рекомендуемый контект:


Похожая информация:

Поиск на сайте:


© 2015-2019 lektsii.org - Контакты - Последнее добавление

Ген: 0.003 с.