Решето Эратосфена
Решето Эратосфена
Одним из способов нахождения простых чисел, является метод, который называется «Решето Эратосфена». Онлайн разложение числа на простые множители можно провести здесь. Чтобы узнать что такое простые числа, просто прочитай эту статью.
Число называется простым, если оно делится только на 1 и само себя
Вроде бы всё просто. но недостатком является то, что нет математической формулы, которое позволяет убедиться, является число простым или нет.
Представьте число 191 587.Не существует формулы, чтобы определить, является ли оно простым!
Для этого нужно определить, есть ли в нем делители и, следовательно, составные.
Легко проверить, имеют ли первые несколько простых чисел (2, 3, 5, 7, 11) делители, используя критерии делимости. Но это не так просто для больших чисел.
Представьте, что нужно проверить все делители такого большого числа! Это очень сложно! Но есть быстрый способ определения простых чисел, который разработан греческим математиком Эратосфеном (3 век до н.э.). Этот метод называется «Решето Эратосфена». Рассмотрим, как это работает, найдя все простые числа от 1 до 100 .
Идея состоит в том, чтобы найти в таблице числа, кратные простым числам и отбросить их как составные. Числа, которые остались, будут простыми числами.
Решето Эратосфена останавливается, когда квадрат числа, которое мы тестируем, больше, чем последнее число в сетке (в нашем случае 100).
Поскольку 11 в квадрате равно 121 и 121 > 100, когда мы доберемся до числа 11, мы можем перестать смотреть.
Простые числа от 1 до 100 с решетом Эратосфена.
Начнем с размещения чисел от 1 до 100 в таблице, подобной этой.
Таким образом, очень легко создавать шаблоны, которые делают для нахождения простых чисел.
Сначала выделяем единицу, которая не является простым числом.
Далее мы ищем числа, кратные 2 и зачеркиваем их (оставляя 2, так как мы знаем, что он имеет только делители 1 и 2 и, следовательно, является простым). Все зачеркнутые числа будут составными.
Для наглядности я буду зачеркнутые составные числа делать светлым цветом.
Теперь из оставшихся чисел мы ищем кратные 3 и зачеркиваем их (кроме 3, поскольку оно простое). Простой способ сделать это, считая по три.
Делаем числа, кратные трем, светлым цветом и оставшихся чисел станет еще меньше.
Теперь пришло время искать кратные 5 . Нам не нужно искать кратные 4, потому что все кратные 4 также кратны 2, поэтому мы уже зачеркнули их. Легко найти кратные 5, все они заканчиваются на 0 или 5. Мы не зачеркиваем 5, потому что это простое число.
Зачеркнутые числа снова делаем светлым цветом.
Давайте перейдем к коэффициентам 7 (число 6 = 2 x 3, а значит оно составное и мы уже нашли кратные 2 и 3). Мы не зачеркиваем 7, так как это простое число. Кратных семи всего в таблице осталось 3 числа — это 49, 77 и 91. Зачеркиваем их.
И опять же для наглядности изменяю цвет зачеркнутых чисел.
Должны ли мы искать кратные 8, 9 и 10? Поскольку эти числа составные и кратны числам, которые мы уже искали, мы можем перейти к цифре 11. Мы уже установили, что остановимся на цифре 11, так что это означает, что мы закончили!
Список простых чисел от 1 до 100
Поэтому мы можем определить, что числа, которые мы не зачеркнули или которые синего и красного цветов, являются простыми числами. Итак, теперь у нас есть список простых чисел от 1 до 100:
2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89 и 97.
Видите, как легко с помощью этого метода искать простые числа!
Источник
Объясните способ отыскания простых чисел с помощью решета эратосфена
- Главная
- Список секций
- Математика
- ПРОСТЫЕ ЧИСЛА И РЕШЕТО ЭРАТОСФЕНА
ПРОСТЫЕ ЧИСЛА И РЕШЕТО ЭРАТОСФЕНА
Автор работы награжден дипломом победителя 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 человек. Результаты оказались следующими.
Вопрос
«да»
«нет»
Знаете ли вы что такое решето?
Знаете ли вы какие числа называются простыми?
Знаете ли вы кто такой Эратосфен?
Знаете ли вы что такое «решето Эратосфена»?
Источник
