Презентация по информатике на тему _Решето Эратосфена_ 11 класс

1. Решето Эратосфена.

2.

Решето Эратосфена - это алгоритм,
который позволяет фильтровать простые
числа (не имеющие делителей кроме
самого себя и единицы) и составные (все
остальные). Название "решето" произошло
из-за того, что древние греки писали числа
на дощечках, покрытых восков и делали
отверстия в тех местах, где оказывались
простые
числа.
Посмотрим,
как
размышляли древнегреческие математики:

3.

1. Выписываем числа от 2 до 15 в ряд
(цифру 1 пропускаем - у неё особые
отношения с миром простых чисел)

4.

2. Берем число 2 и зачеркиваем в
ряду все числа, которые на него
делятся: 4,6,8,10,12,14.
3.
Повторяем этот процесс с
числами 3,5 и понимаем, что
вычеркивать больше нечего.
4.
Получаем
простые
числа
2,3,5,7,11,13.

5.

За
тысячи
лет
математики
придумали
большое
количество
вариаций алгоритма Эратосфена намного увеличили его скорость и
уменьшили затраты памяти, однако в
истории
решето
Эратосфена
останется
первым
и
непревзойденным!

6.

Целое
положительное
число
называется простым, если оно имеет
ровно два различных натуральных
делителя — единицу и самого себя.
Единица простым числом не считается.

7.

Решето Эратосфена (англ. sieve of
Eratosthenes) — алгоритм нахождения всех
простых чисел от 1 до n.
Основная идея соответствует названию
алгоритма: запишем ряд чисел 1,2,…,n, а
затем будем вычеркивать
сначала числа, делящиеся на 2, кроме
самого числа 2,
потом числа, делящиеся на 3, кроме самого
числа 3,
с числами, делящимися на 4, ничего делать
не будем — мы их уже вычёркивали,
потом
продолжим вычеркивать числа,
делящиеся на 5, кроме самого числа 5,
…и так далее.

8.

ДЗ
Число 35.