«Простые числа и Решето Эратосфена»

АВТОНОМНОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ

ШКОЛА №6

РЕФЕРАТ

По дисциплине: Математика

«Простые числа и

Решето Эратосфена»

Выполнил:

Ученик 5 «В» класса

Шустов Павел

Руководитель проекта:

Потехина Т.В.

Долгопрудный

2018 год

Содержание.

1. Введение.
2. Реферат

1. История изучения простых чисел. История появления «решета Эратосфена».
2. Теоретическая часть. Простые числа-близнецы и их виды. Доказательство бесконечного ряда простых чисел.
3. Практическая часть: Деревянная простая модель «решета Эратосфена, Модель «решета Эратосфена со световыми эффектами». Демонстрация алгоритма формирования «решета Эратосфена на примере модели со световыми эффектами»

3. Заключение.
4. Приложения.
5. Список использованной литературы.

I. Введение.

На уроках математики, когда мы изучали тему «Простые и составные числа», я заинтересовался историей данного вопроса. Мне хотелось  больше узнать о том, какие закономерности существуют в натуральном рЯде простых чисел, и подробности работы алгоритма формирования решета Эратосфена.

Немного позже я прочитал в книге «В лабиринте чисел» В. Лёвшина и Э. Александровой о «решете Эратосфена», и как он просеивал, словно муку, простые и составные числа. Данный механизм показался мне очень интересным. Я поинтересовался у друзей и одноклассников, знают ли они, кто такой Эратосфен и что такое «решето Эратосфена» и выяснил, что мало кто знает подробности данного метода, а об Эратосфене слышали только несколько слов на уроках математики.

Поэтому, я считаю данную тему очень актуальной и как только у меня появилась возможность подготовить проект по математике, я нисколько не сомневался в выборе темы. Я хочу рассказать об Эратосфене, простых числах и группах, в которые они объединяются, а так же об алгоритме формирования таблицы простых чисел  и показать модели, которые я выполнил с помощью своих родителей.

Сейчас давайте сформулируем цель работы: 

Изучить алгоритм построения  «решета Эратосфена» и изготовить его материальные модели.

Для достижения данной цели нам нужно будет решить следующие задачи:

1. Изучить литературу по данному вопросу.
2. Изготовить материальные модели «решета Эратосфена»
3. Провести исследования на практике, каким образом работает алгоритм Эратосфена по формированию таблицы простых чисел.

II. 1. История изучения простых чисел.

История появления «решета Эратосфена.

Вопросом изучения простых чисел, закономерности их появления и поиском самого большого простого числа математики занимаются очень давно.

Свойства простых чисел впервые начали изучать математики древней Греции.

Давайте узнаем, какие ученые интересовались данных вопросом и кто из них смог сделать главные открытия в области простых чисел и способов их определения.

Пифагор (VI в. до н.э.) и его ученики изучали вопросы делимости чисел. Я считаю, что это были первые попытки распределения чисел на какие-либо группы по критериям делимости.

Следующий ученый, который работал над вопросом, касающимся простых и составных чисел был математик Евклид (III век до н.э.). Его интересовал вопрос, существует ли последнее (самое большое) простое число. В своей книге «Начала», бывшей на протяжении 2000 лет основным учебником математики, доказал, что простых чисел бесконечно много, т.к. за каждым простым числом есть большее простое число. Доказательство данной теоремы мы рассмотрим в следующей главе.

Пафнутий Львович Чебышев (1821-1894 гг.) доказал более сильную теорему, чем Евклид. Тем самым внес сильных вклад в тему простых чисел.

Вернемся снова к III веку до н.э. Греческих ученых так же интересовал способ отыскивания простых чисел. Самые главные открытия в данной области сделал Эратосфен Киренский.  Ему принадлежит алгоритм составления таблицы простых чисел. Поэтому давайте остановимся  подробнее и узнаем, кто же такой Эратосфен.

Эратосфен Киренский (276 г. до н.э. – 194 г. до н.э.) –греческий математик, астроном, географ, филолог и поэт. Первый известный ученый, который вычислил размеры Земли.

Начальное образование Эратосфен получил в Александрии. Перебравшись затем в Афины, он так тесно сблизился со школой Платона, что обыкновенно себя называл платоником. В результате обучения в двух таких центрах Эратосфен стал высоко-эрудированным человеком, кроме сочинений по математическим наукам, он писал еще трактаты «о добре и зле», о комедии и другие.

Благодаря своему широкому образованию и разнообразию интересов Эратосфен получил от Птолемея III Эвергета приглашение вернуться в Александрию, чтобы стать воспитателем наследника престола и возглавить Александрийскую библиотеку. Эратосфен принял это предложение и в возрасте около тридцати лет занимал должность библиотекаря вплоть до своей кончины. Его научные таланты удостоились высокой оценки современника Эратосфена , Архимеда, который посвятил ему свою книгу «Эфодик» (т.е. метод).

В своих трактатах Эратосфен применял знания математики для различных других наук. Он представил первое научное изложение математической и физической географии. Он вычислил длину земного экватора, измерив углы падения солнечных лучей в Александрии и в Сиене (это современный Асуан), а также узнал расстояние между этими египетскими городами.

Эратосфен успешно использовал математику и в истории. Он знал, что от эпохи Пифагора и Фалеса его отделяют примерно 300 лет. Далее опираясь на составленный им список победителей олимпийских игр, Эратосфен разработал точную хронологическую таблицу, в которой все известные ему политические и культурные события датировал по олимпиадам, т.е. четырехлетним периодам между играми.

В одном из своих трудов Эратосфен нашел способ отделять простые числа от сложных, т.е. составных. Это и было главное из первых открытий в области простых чисел, которым пользуются люди до сих пор.

Каким же способом он их отделял? Он их просеивал сквозь решето. «Решето Эратосфена» - выражение образное, иносказательное. Хотя поначалу способ этот походил на решето и в прямом смысле. Написав, на покрытой воском дощечке ряд натуральных чисел, Эратосфен протыкал острой палочкой составные, и вскоре дощечка покрывалась проколами, хотя и не сквозными. Поэтому данный метод так и называется.

А теперь давайте выясним, каким образом далее развивался вопрос простых чисел и рассмотрим алгоритм действия «решета Эратосфена» на практике.

2. Теоретическая часть.
3. Простые числа и группы, в которые они объединяются. Доказательство бесконечного ряда простых чисел.

Множество натуральных чисел разбивается на три части:

1. число 1 (имеет единственный делитель)
2. простые числа (имеют 2 делителя: 1и само себя)
3.  составные числа (имеют больше 2 делителей)

Эратосфен изобрел системный подход, другими словами алгоритм,  составления списка простых чисел.

В известном трактате «Решето» Эратосфен изложил упрощенную методику определения простых чисел (данную методику мы подробнее рассмотрим на конкретном примере в практической части) и заметил, что многие простые числа группируются в пары «близнецов», например, такие как  и 11 и 13, 29 и 31, 41 и 43. Поэтому я считаю нужным еще разобраться, что же такое дружественные числа или числа - близнецы.

Два простых числа, которые отличаются на 2, как например 5 и 7, 11 и 13, 17 и 19, получили образное название «близнецы». 

Любопытно, что в натуральном ряду имеется даже «тройня». Это числа 3, 5 и 7. Сколько всего чисел – близнецов существует? Данная задача не покорилась ни Эратосфену, ни современным ученым.

По мере удаления от нуля близнецов становится все меньше и меньше, хотя исследования, проводимые «в глубоком числовом космосе», продолжаются выявлять эти замечательные и загадочные пары. На 1996 г. Рекордсменами считались близнецы

242 206 083 * 2 38 880 ± 1,

найденные естественно с помощью компьютера. Сейчас наибольшими известными простыми числами-близнецами являются

2 996 863 034 895 * 21290000 ± 1 .

Они были найдены в сентябре 2016 года в рамках проекта добровольных вычислений PrimeGrid. Данное числа представляют из себя числа, состоящие из 388 342 цифр.

Науке так же известны числа-триплеты. Это тройка различных простых чисел, разность между наибольшим и наименьшим из которых минимальна. Наименьшими простыми числами, удовлетворяющими данному условию, являются – (2,3,5) и (3,5,7). Данная пара простых триплетов исключительна, т.к. в во всех остальных случаях разность между первым и третьим членом равна 6. Числа-триплеты, мы можем выразить следующим образом в виде .

(p, p+2, p+6) или (p, p+4, p+6)

Например, (11, 13, 17), (13, 17, 19)

                   (37, 41, 43), (41, 43, 47)

По состоянию на 2018 год наибольшими известными числами –триплетами являются числа по выше отраженному буквенному выражению,

где p = 6 521 953 289 619*255555 – 5

Данные числа состоят из 16737 цифр. Они были открыты в апреле 2013 года.

Существуют так же простые числа – квадруплеты. Это четверки простых чисел вида:

(p, p+2, p+6, p+8)

Или сдвоенные числа- близнецы.

Например, (5,7,11,13), (101, 103, 107,109) и т.д.

Еще хотелось бы отметить, что секступлеты – это уже шестерки простых чисел, которые мы можем представить в виде буквенного следующего выражения:

(p, p+4, p+6, p+10, p+12, p+16)

Например, (97, 101, 103, 107,109, 113) или (16057,16061, 16067, 16069, 16073).

Теперь давайте обратим внимание на вопрос распределения простых чисел в натуральном ряду. Если посмотрим на натуральный ряд чисел, то мы убедимся, что в пределах от 1 до 100 простые числа встречаются довольно часто, значительно реже в промежутке от 100 до 1000 и по мере удаления от единицы они встречаются все реже и реже. Отсюда может возникнуть мысль, что число простых чисел конечно.

Евклид опроверг это предположение. «Простых чисел существует больше любого указанного числа их». Об этом пишет Евклид в своей книге «Начала» . Вот доказательство этой теоремы.

Предположим, что существует некое наибольшее простое число P. Тогда перемножим все простые числа начиная с 2 и до P. И увеличим полученное произведение на 1.

2 * 3 * 5 * 7 * 11 *… * P + 1 = M

Если число M составное, то оно должно иметь по крайней мере один простой делитель. Но этим делителем не может быть ни одно из простых чисел 2, 3 , 5 ,7 , 11, …, P, поскольку при делении M на каждое из них получаем в остатке 1. Следовательно, число M либо само простое, либо делиться на простое число большее P. Значит, предположение, что существует наибольшее простое число P, неверно и множество простых чисел бесконечно. Простыми словами данное доказательство мы можем сформулировать так: представим, что количество простых чисел конечно. Перемножим их и прибавим 1. Полученное число не делится ни на одно из конечного набора простых чисел, потому что остаток от деления на любое из них дает единицу. Значит, число должно делиться на некоторое простое число, не включенное в набор.

По состоянию на 24 ноября 2014 года, наибольшее известное простое число содержало 17 425 170 знаков. А уже на 26 декабря 2017 года наибольшим известным простым числом стало число 277 232 917 − 1, которое содержит 23 249 425 знаков.

Т.е. Евклид доказал, что между натуральным числом n и n! обязательно найдется  хотя бы одно простое число. В середине XIX века русский математик П.Л. Чебышев доказал более сильную теорему, чем Евклид. Между натуральным числом n и числом в два раза больше его, т.е. 2n содержится хотя бы одно простое число. Т.е. в теореме Евклида число n! заменил на число 2n.

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

3. Практическая часть.

Деревянная модель «решета Эратофена.

Модель «решета Эратосфена» со световыми эффектами.

Демонстрация алгоритма формирования «решета Эратосфена на примере модели со световыми эффектами»

В данной главе я предлагаю поразмышлять, каким образом могло бы выглядеть «решето Эратосфена», как я себе его представляю.

Прежде, чем я покажу Вам модели, которые я изготовил с помощью моих родителей, я хотел бы с Вами поделиться красивой формой «решета Эратосфена» (Приложение 1), которую позаимствовал из старой книги «Математические досуги» М. Гайрдиера. О ней рассказывается в журнале «Квант», который давным-давно читал мой дедушка. Любопытно, что все числа, не вычеркнутые красным или синим, являются простыми, кроме 121. 121 имеет три делителя 1, 11,121. Поэтому оно не является простым.

Теперь давайте рассмотрим алгоритм построения «решета Эратосфена» на примере моих моделей.

Эратосфен придумал остроумный способ составления списка простых чисел. Он записывал все числа от 1 до какого-либо числа, вычеркивал из него числа кратные 2, 3, 5, 7 и т.д. Кроме, разумеется, самого этого числа.  Т.к. древние греки писали на табличках, покрытым воском, а числа не вычеркивали, а выкалывали иглой, то таблица становилась похожей на решето. Написав на покрытой воском дощечке ряд натуральных чисел, Эратосфен протыкал острой палочкой составные, и вскоре дощечка покрывалась проколами. Я попробовал воспроизвести данную табличку своими руками.  Для данного примера я использовал ряд натуральных чисел от 1 до 100. Т.е. N = 100. В ней все ячейки с составными числами имеют отверстия, а простые нет. Таким образом, у меня получилась простая таблица, которая показывает, как может выглядеть «решето Эратосфена».

Сам алгоритм более подробно я продемонстрирую на примере другого макета. Это модель «решета Эратосфена» со световыми эффектами. Для удобства рассмотрим пример для N = 50.

Я изготовил многоквартирный дом, в котором живут числа, на каждом этаже данного дома есть окна. Они все пронумерованы и освещены. Окно под номером один горит синим цветом. Все же остальные были ярко освещены красным. Перед нами натуральные числа, в каждом окне по одному числу. По условию единица к простым числам не относится. Но Эратосфен считал иначе, поэтому мы выделим ее синим цветом. В окне с числом 1 горит синий свет. Остальные числа будут с красными окнами. Для удобства будем просеивать только 5 этажей, а другие пусть просеивает, тот, кто захочет. Сперва давайте погасим каждое второе окно после номера 2. Т.е. 2 это наименьшее число, кратное 2. Его мы оставим не погашенным. В остальных окнах кратным 2 свет мы выключаем. Давайте посмотрим, что же погасло.

4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24, 26, 28, 30, 32, 34, 36, 38,40, 42, 44, 46, 48,50

Теперь давайте погасим каждое третье окно, кроме наименьшего из них, т.к. самого третьего окна. Как мы наблюдаем, некоторые из них уже погашены. Например. 6, 12. Но это не проблема. Мы будем считать, что мы выключили свет в таких окнах два раза.

Что выключили в этот раз?

6, 9, 12, 15, 18, 21, 24, 27, 30, 33, 36, 39, 42, 45, 48

Теперь давайте посмотрим, какое окно осталось не погашенным после 3. Это окно под номером 5. Вот и погасим все окна, кратные пяти, кроме него самого.

10, 15, 20, 25, 30, 35, 40, 45, 50

Учитываем также, что некоторые из этих номеров тоже уже погашены.

Среди непогашенных окон осталось совсем немного для нашего примера, а точнее 3, поэтому предлагаю отключить их одной кнопкой.

Хотя механизм формирования «решета Эратосфена подразумевает выключение окон кратных 7, их номера следующие

14, 21, 28, 35, 42, 49

А далее, как вы уже догадались, будут выключаться окна, кратные 11.

Но в нашем случае далее нет смысла выключать свет, т.к. все окна имеющие номера, равные составным числам уже темные. В них свет не горит.

Что же у нас получилось? У нас получилась таблица простых чисел. Все окна, где номера – простые числа остались освещены.

Таким образом, пользуясь алгоритмом Эратосфена, мы как бы отсеяли, пропустили через решето все составные числа и оставили только простые.

Мы использовали для этого практические модели.

III. Заключение.

В данном работе мы рассмотрели вопросы, касающиеся алгоритма построения «решета Эратосфена», изучили литературу по данной теме, изготовили две материальные модели и на практике с помощью изготовленных моделей построили таблицу простых чисел Эратосфена. Следовательно, цель нашей работы достигнута.

В ходе проделанной работы я сделал следующие выводы, что «решето Эратосфена» работает как своего рода счетная машина. И она работает по определенному алгоритму. Данный алгоритм заключается в следующем: выписывается ряд натуральных чисел, начиная с 2. Двойку отбирают в коллекцию простых чисел, а остальные числа, кратные двум, зачеркиваются. Ближайшим не зачеркнутым числом будет 3. Его тоже отбирают в коллекцию, а все остальные числа, кратные трем, вычеркивают. Некоторые из них уже окажутся зачеркнутыми. Переходят к следующему не зачеркнутому числу и зачеркивают все числа, кратные ему, кроме него самого. Повторяя эту процедуру снова и снова, в конце концов можно добиться того, что не зачеркнутыми останутся лишь простые числа. Они словно просеиваются сквозь решето. На примерах, которые я привел, мы достаточно наглядно проследили механизм отсеивания простых чисел сквозь «решето Эратосфена».

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

Насколько гениален был человек, который в III веке до н.э. предложил для решения своей задачи применить принцип работы вычислительной машины. Возможно, он путешествовал во времени?

IV. Приложения.

1. Красивая форма «решета Эратосфена».

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        31

32        33        34        35        36        37

38        39        40        41        42        43

44        45        46        47        48        49

50        51        52        53        54        55

56        57        58        59        60        61

62        63        64        65        66        67

68        69        70        71        72        73

74        75        76        77        78        79

80        81        82        83        84        85

86        87        88        89        90        91

92        93        94        95        96        97

98        99        100        101        102        103

104        105        106        107        108        109

110        111        112        113        114        115

116        117        118        119        120        121

V. Список использованной литературы.

1. Эм. Александрова, В. Лёвшин. В лабиринте чисел. Издательский дом Мещерякова. 2016г.
2. Квант. №1. 1974г.
3. Математика. № 5. 2007г.
4. Энциклопедия для детей . Т. 11. Математика. – М.: Аванта +, 2002г.
5. Интернет – ресурсы.
6. С. Акимова. Занимательная математика. Нескучный учебник. - Санкт-Петербург. Тригон. 1998г.
7.  В. Лёвшин. Три дня в Карликании. Издательский дом Мещерякова. 2016г.