Лекции.Орг
Лекции.Орг
 

Категории:

Астрономия
Биология
География
Другие языки
Интернет
Информатика
История
Культура
Литература
Логика
Математика
Медицина
Механика
Охрана труда
Педагогика
Политика
Право
Психология
Религия
Риторика
Социология
Спорт
Строительство
Технология
Транспорт
Физика
Философия
Финансы
Химия
Экология
Экономика
Электроника

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



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


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

© 2015-2017 lektsii.org - Контакты

Ген: 0.004 с.