Решето Ерастофена

                 Міністерство освіти і науки України[pic 1]

Державний вищий навчальний заклад «Київський національний економічний університет імені Вадима Гетьмана»

                Кафедра ком’ютерної математики та інформаціїної безпеки

Реферат

з навчальної дисципліни

«Числовий аналіз»

Тема:

«Решето Ерастофена»

Виконала  студентка

2 курсу групи ІК-201

Репік Анастасія Василівна

Перевірила

Чугаєва О.В

   План[pic 2]

1 Вступ

2 Алгоритм

3 Приклад для n = 30

4 Псевдокод

5 Складність алгоритму

6 Модифікації методу

6.1 Необмежений, поступовий варіант

6.2 Перебір дільників

6.3 Сегментоване решето

6.4 Решето Ейлера

6.5 Решето тільки по непарних числах

6.6 Зменшення обсягу споживаної пам'яті

6.7 Решето Ератосфена з лінійним часом роботи

6.7.1 Псевдокод

7 Складність алгоритму на практиці

8. Опис способу "Решето Ератосфена"

9.Висновок

10. Література

Вступ

Ератосфен ( близько 276-194 до н. е..) - грецький письменник і вчений. Ератосфен народився в Африці, в Кірені. Навчався спочатку в Олександрії, а потім в Афінах.

Він керував Олександрійської бібліотекою і був вихователем спадкоємця престолу. Ератосфен був дуже освіченим і різнобічною людиною, він займався філологією, хронологією, математикою, астрономією, географією, сам писав вірші. Ератосфен заклав основи математичної географії, обчисливши з великою точністю величину земної кулі.

В математиці Ератосфена цікавило питання про те, як знайти всі прості числа серед натуральних чисел від 1 до . (Ератосфен рахував 1, простим числом. Зараз математики вважають числом 1 особливого виду, яке не відноситься ні до простих, ні до складових чисел.) Він придумав спосіб отримання всіх простих чисел, який відомий як «Решето Ератосфена».

История

Решот Ератосфе́на - алгоритм нахождения всіх простих чисел до некоторого цілого числа n, які приписують древнегреческому математику Ератосфену Киренскому [1]. Як і у багатьох випадках, тут називається алгоритм говорить про принципі його роботи, то є решето розуміння фільтрації, в даному випадку фільтрації всіх чисел для виключення простих. По мірі проходження списки нумерація залишається, а ненужні (вони називаються складовими) виключаються.

Назва «решето» метод отримав тому, що, згідно з легендою, Ератосфен писав числа на дощечці, вкритій воском, і проколював дірочки в тих місцях, де були написані складові числа. Тому дощечка була якоюсь подобою решета, через яке «просівали» всі складові числа, а залишалися тільки числа прості. Ератосфен дав таблицю простих чисел до 1000.

Алгоритм

Анімація кроків алгоритму Ератосфена для знаходження простих чисел до 120

Для знаходження всіх простих чисел не більше заданого числа n, дотримуючись методу Ератосфена, потрібно виконати наступні кроки:

Виписати підряд всі цілі числа від двох до n (2, 3, 4, ..., n).

Нехай змінна p спочатку дорівнює двом - першому простому числу.

Закреслити в списку числа від 2p до n вважаючи кроками по p (це будуть числа кратні p: 2p, 3p, 4p, ...).

Знайти перше незачёркнутое число у списку, більше ніж p, і привласнити значенням змінної p це число.

Повторювати кроки 3 і 4, поки можливо.

Тепер все незачёркнутие числа в списку - це все прості числа від 2 до n.

На практиці, алгоритм можна поліпшити в такий спосіб. На кроці № 3 числа можна закреслювати починаючи відразу з числа p2, тому що всі складові числа менше нього вже будуть закреслені до цього часу. І, відповідно, зупиняти алгоритм можна, коли p2 стане більше, ніж n. [2] Також, всі прості числа (крім 2) - непарні числа, і тому для них можна вважати кроками по 2p, починаючи з p2.