Общий метод "просеивания" или "пропускания через решето". Решето Сильва - Сильвестра

СодержаниеВведение 3
Основные положения метода просеивания 4
Формула включения и исключения 4
Общий метод "просеивания" или "пропускания через решето". Решето Сильва - Сильвестра 6
Использование общего метода решета в теории чисел 9
Решето Эратосфена, решето Сундарама и решето Аткина 12
Тесты простоты 17
Заключение 19
Список литературы 20
ВведениеАктуальность темы настоящей работы определяется той ролью, которую с каждым годом в науке и практике приобретает один из разделов дискретной математики - комбинаторика. Значение комбинаторики возрастает в связи с использованием ее в теории вероятностей, математической логики, теории чисел, вычислительной технике, кибернетике.
С комбинаторными вычислениями приходится иметь дело представителям многих специальностей, и круг применения методов этого радела дискретной математики с каждым годом будет только увеличиваться. В связи с этим знание основных принципов и методов этого раздела математики, приобретает не только теоретическое но и практическое значение.
Настоящая работа посвящена изучению одного из важных методов комбинаторики - метода "просеивания".
Целью работы является изучение порядка применения метода "просеивания" для подсчета количества простых чисел.
Для достижения этой цели необходимо решить следующие задачи.
- рассмотреть формулу включения и исключения;
- ознакомится с общим методом "просеивания" или "пропускания через решето";
- описать использование общего метода решета в теории чисел;
- рассмотреть особенности методов решета таких ученых как Сильва-Сильвестра, Эрастофена, Сундарама и Аткина;
- описать так называемые тесты простоты.
Список литературы1. Биллинг. В.А. Процедуры и функции - методы класса: Лекция // [WWW-документ] Режим доступа: http://www.intuit.ru/department/pl/tincsharp3/5/5.html
2. История математики под ред. А.П. Юшкевича т.1.-М.:Наука,1970.352с.
3. История математики под ред. А.П. Юшкевича т.2.-М.:Наука,1970.301с.
4. Кофман А. Развитие методов пересчета // Введение в прикладную комбинаторику - М.: Наука, 1975.