Исследовательская работа "Решето Эратосфена"

Управление образования

Муниципальный конкурс исследовательских и проектных работ обучающихся образовательных учреждений

Муниципальное общеобразовательное бюджетное учреждение

«Средняя общеобразовательная школа №1

им. Героя Советского Союза Н.И. Кузнецова» г. Кудымкара»

математика

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

Харин Иван Артёмович, 6 «В» класс

Шпис Вера Михайловна,

учитель математики

Кудымкар, 2023

Содержание

Введение………………………………………………….………………стр. 3

Глава 1…………………………………………………….……................стр. 4 1.1.Исторические сведения о числах……………………….........стр. 4

Глава 2…………………………………………………………………….стр. 5

2.1. Биография Эратосфена……………………………………….стр.5

2.2. Открытие и использование «Решета Эратосфена»……..…..стр. 6 2.3. Анкетирование………………………………………….…….стр. 7

Заключение……………………………………………………………….стр. 9

Список литературы………………………………………………………стр. 10

Приложение………………………………………………………………стр. 11

Введение.

«Миром правят цифры!»

Пифагор

 Числа с далёких времён играют важную роль в жизни человечества. В действительности,  числа не только что-то сравнивают, вычисляют, измеряют. Они могут, оказываться, рисовать, проектировать, сочинять, играть, делать умозаключения и выводы. Ничего удивительного, что они всегда вызывали особое внимaние к себе со стороны человечества. Числам древние люди всегда приписывали особые, сверхъестественные свойства.

В настоящее время простые числа используются в разных областях: шифрование, нанотехнологии, программирование и во многих других. Простые числа помогают людям быть точнее в этих областях, а сейчас точность очень важна. В нанотехнологиях, например: в эти проекты вложены большие деньги, одно неверное действие – и эти вложения не принесут пользы.
Программирование: набрал не ту цифру – и придётся программировать заново. Одна ошибка может запросто разрушить многодневную работу.

Изучая тему «Простые и составные числа», прочитал термин «Решето Эратосфена». Не зная его, решил изучить лучше этот способ, ознакомиться с биографией Эратосфена,

Гипотеза – обучающие не знают о способе нахождения простых чисел - решето Эратосфена, оно не применяется в жизни.

Объект исследования: простые числа Предмет исследования: метод «Решето Эратосфена».

Цель: Изучить метод нахождения простых чисел «Решето Эратосфена».

Задачи:

1. Изучить литературу о нахождения простых чисел;

2. Научиться применять метод «Решето Эратосфена»;

3. Приготовить наглядную демонстрацию метода «Решето Эратосфена».

4. Узнать, где применяется «Решето Эратосфена»

Методы

1. Теоретический (изучение специальной литературы и интернет ресурсов)

2. Обобщение и систематизация материала по данной теме.

3. Эмпирический (пpоведение социального опроса).

Глава 1

1.1. Исторические сведения о числах

Простое число - натуральное число, имеющее ровно два различных натуральных делителя. Другими словами, натуральное число p является простым, если оно отлично от 1 и делится без остатка только на 1 и на само p.

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

Числа-близнецы (парные простые числа) - пары простых чисел, отличающихся на 2 (3,5; 5,7; 11,13…139, 149 и 151).

«Простые числа подобно звёздам на небосводе сияют в числовом космосе». Эта фраза и послужилa толчкoм к тому, чтобы действительно отыскать созвездия простых чисел.

Много веков к простым числам приковано внимание математиков – их ищут, исследуют, находят им применение. Евклид и Эратосфен, Л. Эйлер и К. Гаусс, Рамануджан и Харди, П. Л. Чебышёв и А.И. Виноградов... Этот перeчень выдaющихся учёных занимавшихся простыми числами, а также, задачами связанными с ними можно продoлжать и прoдолжать. (Приложение 1) [4]

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

2*3+1=7

2*3*5+1=31

2*3*5*7+1=211

2*3*5*7*11+1=2.331и т. д.

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

Глава 2

2.1. Биография Эратосфена

Эратосфен - древний математик, живший в 276-194 годах до нашей эры. Он является одним из самых разносторонних ученых античности. История сохранила краткие сведения из биографии Эратосфена, однако некоторые сведения дошли до наших времён.

Эратосфен Сын Эглаоса, уроженец Кирены (один из величайших городов античности, город, посвящённый Аполлону, стоял на территории современной Ливии).

Начальное образование Эратосфен получил в Александрии под руководством своего учёного земляка Каллимаха. Другим учителем Эратосфена в Александрии был философ Лизний. Перебравшись затем в Афины, он так тесно сблизился со школой Платона, что обыкновенно называл себя платоником. Результатом изучения наук в этих двух центрах была энциклопедическая эрудиция Эратосфена; кроме сочинений по математическим наукам, он писал ещё трактаты «о добре и зле», о комедии и много ещё трактатов. Из всех своих сочинений Эратосфен придавал особенное значение литературным и грамматическим, как это можно заключить из того, что он любил называть себя филологом.

Царь Птолемей III Эвергет после смерти Каллимаха вызвал Эратосфена из Афин и поручил ему заведование Александрийской библиотекой. Удалённый в старости от этой должности, Эратосфен впал в крайнюю нищету и, страдая болезнью глаз или даже совсем ослепнув, уморил себя голодом.

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

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

В честь Эратосфена назван кратер на  Луне.

2.2. Открытие и использование «Решето Эратосфена».

Несмотря на малую информацию об Эратосфене, на него очень часто ссылались авторитетные и знаменитые мудрецы, философы античности: Архимед, Страбон и другие. Родился Эратосфен в Африке, в Кирене, поэтому нет ничего удивительного в том, что своё образование он начал в Александрии. Живой ум Эратосфена пытался постичь практически все известные на тот момент науки. И как все учёные, он наблюдал за природой. [2]

Он работал во многих отраслях древней науки, занимался хронологией, астрономией, географией, философией и музыкой (Приложение 2).

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

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

Он писал на папирусе, натянутом на рамку, или на восковой дощечке. Не зачёркивал, а прокалывал составные числа. Получалось нечто вроде решета, через которые «просеивались» составные числа.

Сущность способа заключается в следующем:

- в записи натуральных чисел, сначала вычёркивается 1.

- число 2 – простое, вычёркиваются все числа, делящиеся на 2 (4,6,8, и т.д.).

- число 3- простое, вычёркиваются числа, делящиеся на 3 (6, 9, 12 и т.д., попадают уже зачёркнутые)

- число 5-первое не зачёркнутое число –будет простым. Продолжая аналогичным способом можно найти сколь угодно большой отрезок последовательности простых чисел. (Приложение 3).

Решето Эратосфена используется на информатике в качестве наиболее актуального способа вычисления последовательностей, путем интегрирования аксиомы в программный код. Несмотря на древность открытия, данная теория помогает быстро и эффективно освоиться в труднодоступных расчетах. Очевидно, что компьютерная реализация «решета Эратосфена» требует большого объёма памяти. Так оно и было, пока своё решение проблемы не предложил современный 38-летний перуанский математик в Харальд Хельфготт, которому удалось предложить улучшенный вариант «решета Эратосфена» — метода поиска простых чисел. (Приложение 4) [3]

Новый вариант в компьютерной реализации требует меньше оперативной памяти, что означает меньший объём подкачки страниц из виртуальной памяти — следовательно, процесс существенно ускоряется. (Приложение 5).

2.3. Анкетирование

Для изготовления «решета Эратосфена» я взял лист бумаги формата А4. Начертил сетку, в каждой клетке записал натуральные числа от 1 до 168. Используя алгоритм построения «Решета Эратосфена», я зачёркивал те числа, которые были кратны простым. (Приложение 6)

Для практической части провёл опрос своих одноклассников. Тема «простые и составные числа» уже изучена. Им были предложены 3 вопроса: дать определение простыми и составными числам, и знают ли они метод «Эратосфена». (Приложение 7)

Вопрос: какие числа называются простыми?

На вопрос не смогли ответить, не помнят

Вопрос: какие числа называются составными?

С заданием справились только 5 человек, остальные не знают.

Вопрос: знаете ли вы метод «Решето Эратосфена» и где оно встречается?

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

Заключение.

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

Итак, я узнала, что «Решето Эратосфена» используется в современной жизни программистов и в жизни школьников, а также, что Харальд Хельфготт смог оптимизировать его, для меньшего расхода памяти на компьютере.

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

Список литературы.

1. Виленкин Н.Я. Математика. 6 класс : учеб. Для общеобразоват. Учреждений / –М.: Мнемозина, 2019.

2. Грасиан Э. Простые числа. Долгая дорога к бесконечности. Мир математики. / Энрике Грасиан. - М.: ООО «Де Агостини», 2014. – 64 с.

3. С.Коутинхо. Введение в теорию чисел. Алгоритм RSA. Москва: Постмаркет, 2001. - 328 с

4. Грасиан Энрике  Простые числа [Долгая дорога к бесконечности] https://math.wikireading.ru/16

Приложение

Приложение 1

Евклид Леонардо Эйлер (1707-1783)

Иога́нн Га́усс (1777 —1855) П. Л. Чебышев. (1821 г. -1894)

Приложение 2

Эратосфен

Приложение 3

Приложение 4

Перуанский математик Харальд Хельфготт

Приложение 5

vectorbool sieve(int n) {

vectorbool is_prime(n+1, true);

for (int i = 2; i n; i++)

if (is_prime[i])

for (int j = 2*i; j n; j += i)

prime[j] = false;

return is_prime;

Нахождение простых чисел в компьютерной версии

Приложение 6

Приложение 7

Анкета.

1. Какие числа называются простыми?

2. Какие числа называют составными?

3. Что такое «Решето Эратосфена» и как его применить?