Презентация "Решето Эратосфена"

Слайд 1

Слайд 2

Математика – царица наук, арифметика – царица математики. К.Ф. Гаусс

Слайд 3

— алгоритм нахождения всех простых чисел до некоторого целого числа n , который приписывают древнегреческому математику Эратосфену Киренскому. Решето́ Эратосфе́на

Слайд 4

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

Слайд 6

Теперь все незачеркнутые числа в списке — простые.

Слайд 7

На практике, алгоритм можно улучшить следующим образом. На шаге № 3, числа можно зачеркивать, начиная сразу с числа , потому что все составные числа меньше его уже будут зачеркнуты к этому времени. И, соответственно, останавливать алгоритм можно, когда станет больше, чем n .

Слайд 8

Неограниченный, постепенный вариант. В этом варианте простые числа вычисляются последовательно, без ограничения сверху, как числа находящиеся в промежутках между составными числами, которые вычисляются для каждого простого числа p начиная с его квадрата, с шагом в p (или для нечетных простых чисел 2p).Первое простое число 2 (среди возрастающих положительных целых чисел) заранее известно, поэтому в этом самореферентном определении нет порочного круга.

Слайд 9

Пример для n =30. Запишем натуральные числа начиная от 2 до 30 в ряд: 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 Первое число в списке, 2 — простое. Пройдём по ряду чисел, зачёркивая все числа кратные 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: 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

Слайд 10

Пример для n =30. Следующее незачеркнутое число, 5 — простое. Пройдём по ряду чисел, зачёркивая все числа кратные 5 : 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 Необходимо провести зачёркивание кратных для всех простых чисел p , для которых p2 ≤ n . В результате все составные числа будут зачеркнуты, а незачеркнутыми останутся все простые числа. Для n = 30 уже после зачёркивания кратных числу 5 все составные числа получаются зачеркнутыми: 2 3 5 7 11 13 17 19 23 29

Слайд 11

В математике есть своя красота, как в живописи и поэзии. Н.Е. Жуковский

Слайд 12

Спасибо за внимание!