Лекции.Орг

Поездка - Медвежьегорск - Воттовара - Янгозеро: По изначальному плану мы должны были стартовать с Янгозера...

Построение спирали Архимеда: Спираль Архимеда- плоская кривая линия, которую описывает точка, движущаяся равномерно вращающемуся радиусу...

Электрогитара Fender: Эти статьи описывают создание цельнокорпусной, частично-полой и полой электрогитар...

 

Категории:


Классификация электровозов: Свердловский учебный центр профессиональных квалификаций...


Деформации и разрушения дорожных одежд и покрытий: Деформации и разрушения могут быть только покрытий и всей до­рожной одежды в целом. К первым относит...


Агроценоз пшеничного поля: Рассмотрим агроценоз пшеничного поля. Его растительность составляют...

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



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


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

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


На сайте можно прочитать про:

Поездка - Медвежьегорск - Воттовара - Янгозеро: По изначальному плану мы должны были стартовать с Янгозера...

Построение спирали Архимеда: Спираль Архимеда- плоская кривая линия, которую описывает точка, движущаяся равномерно вращающемуся радиусу...

Электрогитара Fender: Эти статьи описывают создание цельнокорпусной, частично-полой и полой электрогитар...


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

Ген: 0.004 с.