Решето эратосфена таблица простых чисел

Решето эратосфена таблица простых чисел

    Главная

  • Список секций
  • Математика
  • ПРОСТЫЕ ЧИСЛА И РЕШЕТО ЭРАТОСФЕНА

ПРОСТЫЕ ЧИСЛА И РЕШЕТО ЭРАТОСФЕНА

Автор работы награжден дипломом победителя III степени

Введение

Впервые о простых числах мы узнали в 6 классе на уроке математики, когда изучали тему «Простые и составные числа». Так же на форзаце учебника «Математика-6» имеется таблица простых чисел до числа 997 (Приложение 1). Мы знаем то, что находится на форзаце, имеет важную значимость в изучении данного предмета. И действительно, это подтвердилось при дальнейшем изучении математики

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

Работу начали с анкетирования учащихся 6 – 10 классов нашей школы, чтобы выяснить знают ли они:

1. Что такое решето?

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

3. Кто такой Эратосфен?

4. Что такое «решето Эратосфена»?

В опросе приняли участие 90 человек. Результаты оказались следующими (Приложение 2).

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

Гипотеза: Действительно ли мы можем найти простое число больше 997.

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

Задачи:

1.Изучить имеющуюся литературу по теме проекта.

2.Провести опрос по теме проекта.

3.Найти простые числа, больше числа 997.

4.Изготовить материальную модель решета Эратосфена.

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

Предмет исследования: таблица простых чисел

Методы исследования:

1.Работа с учебной и научно-популярной литературой, ресурсами сети Интернет.

3. Опыты и эксперименты с простыми числами

Этапы проекта:

2. Основная часть

2.1. Краткое описание используемых понятий

Решето – это утварь для просеивания муки, состоящая из широкого обруча и натянутой на него с одной стороны сетки. Решето отличается от сита более крупным размером отверстий сетки. (Толковый словарь Ушакова)

Решето -1) Предмет обихода широкий обруч с натянутой на него частой сеткой для просеивания чего-нибудь

2) Просеивающее устройство. (Толковый словарь Ожегова)

Решето – всякая несплошная вещь со сквозниной, с промежками, пролётами; ряд установленных жёрдочек, шестиков…переплетённых вдоль и поперёк, или иным образом.(Толковый словарь Даля)

Простое число – это натуральное число, которое не имеет других делителей кроме 1 и самого себя. (Пример: число 19 = 1 * 19)

Составное число – это натуральное число, у которого есть делители,отличные от 1 и самого себя. (Пример: число 10 = 5*2)

Всякое составное число можно разложить на простые множители.(Например: 63=3*3*7 или 363= 3*11*11)

Число 1 имеет только один делитель: само это число. Поэтому оно не относит ни к простым, ни к составным числам.

Первым проблему определения простых чисел обозначил и решил древнегреческий ученый Эратосфен Киренский примерно в 220 году до нашей эры, предложив один из алгоритмов определения простых чисел. Этот способ назвали «решето Эратосфена».

В 1909 году американский математик Деррик Норман Лемер опубликовал таблицы простых чисел в промежутке от 1 до 10.017.000. Книга таблиц имеется в Российской государственной библиотеке в Москве.

Еще более титаническую вычислительную работу выполнил профессор Парижского университета славянский математик Якуб Филипп Кулик (01.05.1793- 28.02.1863).Над своей рукописью «Великий канон делителей всех чисел, не делящихся на 2, 3 и 5, и заключенных между ними простых чисел до 100 300 201» он работал последние 20 лет жизни, не имея никакой надежды на его издание. Это произведение до сих пор не напечатано. Оно хранится в библиотеки Венской АкадемииНаук.

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

Вопросом изучения простых чисел, закономерности их появления и поиском самого большого простого числа математики занимаются очень давно. Первые сведения о простых числах, встречаются в трудах древне – греческого математика Эратосфена Киренского (276г.до н.э-194г. до н.э).

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

Читайте также:  Вайбер найти человека по имени и фамилии

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

Его научные таланты удостоились высокой оценки современника Эратосфена, Архимеда, который посвятил ему свою книгу Эфодик (т.е. Метод)

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

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

1.Из ряда чисел: 2,3,4,5,6,7,8,9,10,11,12,13 и т. д вычёркиваем числа кратные 2.

2.Затем, вычёркиваем числа кратные 3.

3.Вычёркиваем числа кратные 4.

4.Вычёркиваем числа кратные 5.

5.Вычёркиваем числа кратные 6 .

6.Делим, пока все составные числа не будут «просеяны», и останутся только простые числа: 2,5,7,11,.13….

Пример

Запишем натуральные числа, начиная от 2 до 20 в ряд.

2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

Первое число в списке 2 — простое. Пройдём по ряду чисел, вычёркивая все числа кратные 2

2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

Следующее не вычеркнутое число 3 — простое. Пройдём по ряду чисел, вычёркивая все числа кратные 3

2 3 5 6 7 9 11 12 13 15 17 19

Процесс окончен. Все незачеркнутые числа последовательности являются простыми.

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

2.4. Практическая часть проекта: изготовление решета Эратосфена

Для изготовления «решета Эратосфена» мы взяли фанеру формата 36*42. Начертили сетку, в каждой клетке записали натуральные числа от 1001 до 1120.

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

Заключение

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

Следовательно – наша цель достигнута, проблема решена. Разработанные нами материалы могут использоваться на уроках математики.

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

Я познаю мир. Детская энциклопедия: Математика/ Я 11 Авт.-сост. А.П. Савин и др.: — М.: ООО «Издательство АСТ», 2001.

Интернет – ресурсы( Википедия)

А.Г. Мерзляк, В.Б. Полонский, М.С. Якир. Учебник «Математика 6 класс»:Издательство «Вентана–Граф», Москва, 2014

Толковый словарь Ушакова

Толковый словарь Ожегова

Толковый словарь Даля

Приложение 1

таблица простых чисел

Приложение 2

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

1. Что такое решето?

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

3. Кто такой Эратосфен?

4. Что такое «решето Эратосфена»?

В опросе приняли участие 90 человек. Результаты оказались следующими.

Вопрос

«да»

«нет»

Знаете ли вы что такое решето?

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

Знаете ли вы кто такой Эратосфен?

Знаете ли вы что такое «решето Эратосфена»?

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

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

Небольшую "коллекцию" простых чисел можно составить старинным способом, придуманный ещё в 3 в. до н. э. Эратосфеном Киренским, хранителем знаменитой Александрийской библиотеки.

Выпишем несколько подряд идущих чисел, начиная с 2. Двойку отберём в свою коллекцию, а остальные числа, кратные 2, зачеркнем. Ближайшим незачёркнутым числом будет 3. Возьмём в коллекцию и его, а все остальные числа, кратные 3, зачеркнем. При этом окажется, что некоторые числа уже были вычеркнуты раньше, как, например, 6, 12 и др. Следующее наименьшее незачёркнутое число – это 5. Берем пятерку, а остальные числа, кратные 5,зачеркиваем. Повторяя эту процедуру снова и снова, в конце концов добьемся того, что незачеркнутыми останутся одни лишь простые числа – они словно просеялись сквозь решето. Поэтому такой способ и получил название "решето Эратосфена".

Читайте также:  Какой ортопедический матрас лучше выбрать отзывы специалистов

Простых чисел бесконечное множество.

2.2 Числа – близнецы

Два простых числа, которые отличаются на 2, как 5 и 7, 11 и 13, 17 и 19, получили название "близнецы". В натуральном ряду имеется даже "тройня" — это числа 3, 5, 7. Ну а сколько всего существует близнецов — современной науке неизвестно.

В пределах первой сотни близнецы – это следующие пары чисел: (3, 5), (5, 7), (11, 13), (17, 19), (29, 31), (41, 43), (59, 61), (71,73). По мере удаления от нуля близнецов становится все меньше и меньше. Близнецы могут собираться в скопления, образуя четверки, например, (5, 7, 11, 13) или (11, 13, 17, 19). Как много таких скоплений – тоже пока неизвестно.

2.3 Проблема Гольдбаха

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

50 = 47 + 3, 46 = 43 + 3, 32 = 29 + 3.

Гольдбах испытал очень много чисел и ни разу не встретил такого числа, которое нельзя было бы разложить на сумму двух или трех простых слагаемых. Но будет ли так всегда, он не доказал. Долго ученые занимались этой задачей, которая названа "проблемой Гольдбаха" и сформулирована так, требуется доказать или опровергнуть предложение:

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

Л. Эйлер ответил Х. Гольдбаху, что он высказывает (без доказательства) еще более интересную догадку: "Всякое четное натуральное число, большее двух, представляет собой сумму двух простых чисел".

12 = 5+ 7; 64 = 59 + 5 = 41 +23 = 47 +17; 28 = 11 + 17 = 23 + 5;

162 = 157 + 5 = 151 + 11 = 139 + 23 = 131 + 31.

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

Глава 3. Фигурные числа

3.1 Фигурные числа

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

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

Различают следующие виды фигурных чисел:

Линейные числа — числа, не разлагающиеся на множители, то есть их ряд совпадает с рядом простых чисел, дополненным единицей: 1, 2, 3, 5, 7, 11, 13, 17, 19, 23, …

Плоские числа — числа, представимые в виде произведения двух сомножителей, то есть составные: 4, 6, 8, 9, 10, 12, 14, 15, …

Телесные числа — числа, представимые произведением трёх сомножителей: 8, 12, 16, 18, 20, 24, 27, 28, …

3.2 Многоугольные числа

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

Последовательность треугольных чисел: 1, 3, 6, 10, 15, 21, 28, 36, 4 и т.д. (1, 1+2=3, 1+2+3=6, 1+2+3+4=10, 1+2+3+4+5=15 и т. д.)

Квадратные числа представляют собой произведение двух одинаковых натуральных чисел, то есть являются полными квадратами: 1, 4, 9, 16, 25, 36, и т.д. (1+3=4, 1+3+5=9, 1+3+5+7=16).

Пятиугольные числа 1, 5, 12, 22, 35, 51, 70, 92, 117, 145

Пирамидальные числа возникают при складывании круглых камушков горкой так, чтобы они не раскатывались. Получается пирамида. Каждый слой в такой пирамиде — треугольное число. Наверху один камушек, под ним — 3, под теми — 6 и т.д.: 1, 1+3=4, 1+3+6=10, 1+3+6+10=20, .

Кубические числа возникают при складывании кубиков: 1, 2·2·2=8, 3·3·3=27, 4·4·4=64, 5·5·5=125. и так далее.

Глава 4. Дружественные, совершенные, компанейские числа

4.1 Дружественные числа

Дружественные числа – это два натуральных числа, для которых сумма всех делителей первого числа (кроме него самого) равна второму числу и сумма всех делителей второго числа (кроме него самого) равна первому числу. По свидетельству античного философа Ямвлиха, великий Пифагор на вопрос, кого считать своим другом, ответил: "Того, кто является моим вторым Я, как числа 220 и 284".

Читайте также:  Проверить apple iwatch по серийному номеру

История дружественных чисел теряется в глубине веков. Эти удивительные числа были открыты последователями Пифагора. Правда пифагорейцы знали только одну пару дружественных чисел – 220 и 284. Проверим эту пару чисел на свойство дружественных чисел:

1 + 2 + 4 + 5 + 10 + 11 + 20 + 22 + 44 + 55 + 110 = 284,

1 + 2 + 4 + 71 + 142 = 220.

Долго считалось, что следующую пару дружественных чисел 17296 и 18416 открыл в 1636 году знаменитый французский математик Пьер Ферма. Но недавно в одном из трактатов арабского ученого Ибн аль-Банны (1256-1321) были найдены строки: "Числа 17296 и 18416 являются дружественными. Аллах всеведущ".

А задолго до Ибн аль-Банны другой арабский математик абу-Хасан Сабит ибн Курра (836-901) сформулировал правило, по которому можно получить некоторые дружественные числа:

если для некоторого n числа p=3·2n-1-1, q=3·2n-1 и r=9·22n-1-1 простые, то числа A=2npq и B=2nr — дружественные.

При n=2, числа p=5, q=11, r=71 простые, и получается пара чисел Пифагора: 220 и 284.

При n=4, числа p=23, q=47, r=1151 простые, и получается пара чисел Ибн аль-Банны и Ферма 17296 и 18416.

При n=7 получается пара чисел, найденная в 1638 году французским математиком и философом Рене Декартом.

После Декарта первым получил новые дружественные числа Леонард Эйлер. Он открыл 59 пар дружественных чисел, среди которых были и нечетные числа, например, 9773505 и 11791935. Он предложил пять способов отыскания дружественных чисел. Эту работу продолжили математики следующих поколений. В настоящее время известно около 1100 пар дружественных чисел. В 1867 году шестнадцатилетний итальянец Никколо Паганини потряс математический мир сообщением о том, что числа 1184 и 1210 дружественные! Эту пару, ближайшую к 220 и 284, проглядели все знаменитые математики, изучавшие дружественные числа.

Пару чисел 220 и 284 стали считать символом дружбы. В Средние века имели хождение талисманы с выгравированными на них числами 220 и 284, якобы способствующими укреплению любви.

Дружественные числа продолжают скрывать множество тайн. Например, есть ли пары, в которых одно число четное, а другое — нечетное? Конечно или бесконечно число пар дружественных чисел? Существует ли общая формула, позволяющая описать все пары дружественных чисел?

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

Рассмотрим в общих чертах работу метода. Дана упорядоченная по возрастанию последовательность натуральных чисел. Следуя методу Эратосфена, возьмем некоторое число P изначально равное 2 – первому простому числу, и вычеркнем из последовательности все числа кратные P: 2P, 3P, 4P, …, iP (iP≤N). Далее, из получившегося списка в качестве P берется следующее за двойкой число – тройка, вычеркиваются все кратные ей числа (6, 9, 12, …). По такому принципу алгоритм продолжает выполняться для оставшейся части последовательности, отсеивая все составные числа в заданном диапазоне.

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

Программная реализация алгоритма Эратосфена потребует:

  1. организовать логический массив и присвоить его элементам из диапазона от 2 до N логическую единицу;
  2. в свободную переменную P записать число 2, являющееся первым простым числом;
  3. исключить из массива все числа кратные P 2 , ступая с шагом по P;
  4. записать в P следующее за ним не зачеркнутое число;
  5. повторять действия, описанные в двух предыдущих пунктах, пока это возможно.

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

Так будет выглядеть псевдокод алгоритма:

Он состоит из двух циклов: внешнего и внутреннего. Внешний цикл выполняется до тех пор, пока P 2 не превысит N. Само же P изменяется с шагом P+1. Внутренний цикл выполняется лишь в том случае, если на очередном шаге внешнего цикла окажется, что элемент с индексом P не зачеркнут. Именно во внутреннем цикле происходит отсеивание всех составных чисел.

Ссылка на основную публикацию
Регистрбухгалтерии хозрасчетный остатки параметры
В 1С:Предприятии 8 для отражения движения различных ресурсов, денежных средств и иных материальных ценностей существует регистр бухгалтерии. Регистр бухгалтерии предназначен...
Протокол udp используется для
Чем отличается протокол TCP от UDP, простым языком Чем отличается протокол TCP от UDP, простым языком Чем отличается протокол TCP...
Протокол интернета версии 4 byfly
Главная Новости Рекомендации пользователям Настройка оборудования и ПО "Мультискрин" от Ростелеком Настройки маршрутизаторов для FTTB Технология FTTC (VDSL) Настройки ADSL...
Регистрация смарт тв филипс
На протяжении многих лет компания Philips остаётся одним из крупнейших производителей телевизоров в мире. Сегодня она занимает третье место после...
Adblock detector