"Об одном видоизменении способа, известного под названием Эратосфенова решета"

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

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

Собинский район Владимирская область

На снимке —

 скульптура абстрактного экспрессиониста

Марка Ди Суверо «Решето Эратосфена»,

установленная в кампусе

Стэнфорского университета

Исследовательская работа

"Об одном видоизменении способа,

известного под названием Эратосфенова решета"

Работу выполнил

ученица 8Б класса

Ермилова Алиса

научный руководитель

Ларионова Вера Ивановна

2013-2014 учебный год

Аннотация

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

Содержание

1. ВВЕДЕНИЕ

Актуальность

В 8 классе мы изучали тему «Квадратные корни». В одном из заданий на данную тему необходимо было вынести множитель из-под знака корня . Конечно, данную задачу в лоб мне решить не удалось. Мне необходимо было разложить число 9648 на простые множители.

Но, оказалось, что сделать это было не так уж просто. При разложении числа 9648 на простые множители мне необходимо узнать, является число 67 простым или составным. Но под рукой у меня не оказалось таблицы простых чисел. Поэтому мне пришлось воспользоваться известным методом нахождения простых чисел – "Решето Эратосфена". Но это у меня заняло много времени. Поэтому возникла проблема, которую я хочу решить в ходе работы: выяснить, решето Эратосфена – единственный способ нахождения простых чисел или есть еще способ? 

Таким образом, объектом моего исследования являются простые числа, а предметом исследования – способ нахождения простых чисел.

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

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

1. Систематизировать знания по теме: "Простые и составные числа";

2. Исследовать закономерности расположения простых и составных чисел.

3. Привести способы нахождения простых чисел.

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

1. обработка и анализ научно-публицистических и учебных изданий по исследуемой проблеме;
2.  метод сравнения и сопоставления полученных фактов.

2.  ТЕОРЕТИЧЕСКАЯ ЧАСТЬ

2.1. Немного о простых числах 

Сразу замечу, что простые числа принадлежат множеству натуральных чисел. Евклид определял простые числа так: "Простое число есть измеряемое только единицей”. Иными словами, простое число — это натуральное число, которое имеет ровно два различных натуральных делителя: единицу и самого себя. Все остальные числа, кроме единицы, называются составными. Таким образом, все натуральные числа, бо́льшие единицы, разбиваются на простые и составные. Число 1 (единица) не причисляется ни к простым, ни к составным числам.

Для начала приведу ряд простых чисел в интервале (1, 500). Сделаю это в форме таблицы, чтобы лучше увидеть, как распределяются простые числа в  ряду натуральных чисел (табл.1). Ячейки, содержащие простые числа, выделены темным цветом.

табл.1. Таблица распределения простых чисел от 1 до 500

Вот так причудливо располагаются простые числа в ряду натуральных чисел!  На первый взгляд может показаться, что простых чисел довольно много только в начале натурального ряда, т. е.  пока числа сравнительно не велики, и что с увеличением чисел простые числа станут постепенно редеть и, наконец, совсем исчезнут. Но тaкоe предположение неверно, в действительности существует бесчисленное множество простых чисел.

Плотность распределения простых чисел среди натурального ряда различна, есть участки, где простые числа располагаются гуще (табл. 2, табл.3).

табл.2. Количество простых чисел в различных промежутках  от 1 до 100

табл.3. Количество простых чисел в различных промежутках  от 100 до 1000

Пестрота картины распределения простых чисел увеличивается еще более, если отметить, что существуют пары простых чисел, которые отделены в натуральном ряду только одним числом («близнецы»). Например. 3 и 5, 5 и 7, 11 и 13, 10016957 и 10016959. С другой стороны, существуют пары простых чисел, между которыми много составных. Например, все 153 числа  от 4652354 до 4652506 являются составными.

Также нельзя по виду числа определить является оно простым или нет. Например, является ли простым число 261-1 ,   22^23+1?  Математик Первушин доказал, что первое число – простое, а второе – составное. Издавна ведутся записи, отмечающие наибольшие известные на то время простые числа. Один из рекордов поставил в своё время Эйлер, найдя простое число 231 − 1 = 2147483647.

Наибольшим известным простым числом по состоянию на февраль 2011 года является 243112609 − 1. Оно содержит 12 978 189 десятичных цифр и является простым числом Мерсенна (M43112609). Его нашли 23 августа 2008 года на математическом факультете университета UCLA в рамках проекта по распределённому поиску простых чисел Мерсенна GIMPS.

Числа Мерсенна выгодно отличаются от остальных наличием эффективного теста простоты: теста Люка — Лемера. Благодаря ему простые числа Мерсенна давно удерживают рекорд как самые большие известные простые.

За нахождение простых чисел из более чем 100 000 000 и 1 000 000 000 десятичных цифр EFF назначила денежные призы соответственно в 150 000 и 250 000 долларов США.

Вывод:

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

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

Составлением таблиц простых чисел занимались математики ещё в глубокой древности. Первая попытка такого рода приписывается александрийскому математику и географу Эратосфену Киренскому, жившему примерно в 276 – 194 г. до н.э.

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

Опишу подробно алгоритм Эратосфена. Пусть нам надо найти все простые числа в диапазоне от 1 до N. Выпишем подряд все числа от 2 до N. Зачеркнём в этом списке каждое второе число из следующих за числом 2. Таким образом, мы отсеем все числа кратные числу 2. Число 2 является первым простым числом. Следующее не зачёркнутое число в списке после числа 2 – число 3. Это второе простое число. Повторим процедуру отсеивания, только теперь будем зачёркивать каждое третье число из следующих за числом 3. Так отсеем все числа кратные 3. Процедуру отсеивания следует повторять до тех пор, пока не доберёмся до простого числа, которое больше квадратного корня из N. Все числа, оставшиеся не зачёркнутыми в списке, будут простыми.

Приведу иллюстрацию описанного метода для N = 100.

Сначала покажу, как будет выглядеть список чисел после отсеивания чисел кратных 2:

Теперь покажу, как выглядит список после вычёркивания всех чисел кратных 3:

Теперь закрасим числа, кратные 5

Осталось вычеркнуть числа кратные 7

В этом примере процедура отсеивания (зачёркивания) завершилась на простом числе 7, то есть последний раз мы зачёркивали в этом списке каждое седьмое число, следующее за числом 7. Числа кратные 11 мы уже не будем зачёркивать (отсеивать), так как это число больше квадратного корня из 50.

Окончательно получим простые числа. Они оказались в таблице незакрашенными, кроме 1.

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

Определенный интерес представляет статья Буняковского «Об одном видоизменении способа, известного под названием Эратосфенова решета» (1882г.). В отличие от Эратосфена Буняковский выделяет из последовательности испытуемых чисел простые числа, рассматривая отдельно числа, оканчивающиеся на 1, на 3, на 7, на 9, и используя при этом решения вспомогательных неопределенных уравнений первой степени (довольно простого вида). Я не разбиралась с этим приемом. Предоставляю данный метод читателям для самостоятельного изучения. В помощь даю ссылку на форум "Портал Естественных Наук” в списке литературы.

В настоящее время составлены таблицы простых чисел, простирающиеся до миллионов.

ПРАКТИЧЕСКАЯ ЧАСТЬ

Еще раз о поиске простых чисел 

Выпишу числа по 10 в строке и в ней закрашу простые числа.

Обращаю особое внимание на то, что не существует простых чисел, оканчивающихся на 4, 6, 8, 0, и что среди простых чисел, оканчивающихся на 2, имеется только одно число — это само 2, и из оканчивающихся на 5 — одно число, т. е. 5. Следовательно, кроме 2 и 5, все остальные простые числа оканчиваются на   1, 3, 7, 9. Но нельзя считать, что числа, оканчивающиеся на 1, 3, 7, 9, обязательно будут простыми, например числа 21, 33, 27, 39 и многие другие — составные.

Вывод: через составные числа можно провести диагональные прямые.

Но при таком зачеркивании некоторые числа, которые делятся на 7 и на 13 остались незачеркнутыми!

Так как остались незачеркнутыми числа, кратные 7, то запишу числа по 6 в строке. Закрашу все простые числа

Вывод: 

Простые числа оказались только в двух столбиках. Числа, делящиеся на 2 и 3 находятся во втором, четвертом и шестом столбиках. Числа, делящиеся на 5, 7, 11 находятся по диагоналям.

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

• Вычеркнем 1, которая  не является ни простым, ни составным числом.

• Вычеркнем все числа, кратные 2 (за исключением самой 2), проведя вертикальные черты во втором, четвертом и шестом столбцах.
• Вычеркнем все числа, кратные 3, (за исключением самой 3), проведя вертикальную черту в третьем столбце. Следующее за 3 не вычеркнутое число равно 5.
• Чтобы вычеркнуть все числа, кратные 5, проведем диагонали, идущие вниз и влево.
• Чтобы вычеркнуть все числа, кратные 7, проведем диагонали, идущие с наклоном вправо и вниз.
• Числа 8,9 и 10 – составные, их кратные уже были вычеркнуты раньше.
• Следующее простое число 11, 11∙11=121. Если бы таблица была больше, то пришлось бы      исключать кратные 11, проводя диагонали с более крутым наклоном. И так далее…

Все не зачёркнутые числа в таблице, кроме числа 1, являются простыми (они выделены синим цветом).

Заключение

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

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

Практическая значимость 

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

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

1. Виленкин
2. Глейзер Г.И. – История математики в школе: IV – VI кл. Пособие для учителей. – М.: Просвещение, 1981.
3. Депман И. – Рассказы о математике. – М. – Л., Детгиз 1954.
4. Карпеченко Е. Тайны чисел. Математика /Приложение к газете "Первое сентября" - №13 - 2007.
5. Крылов А.Н. Числа и меры. Математика/ Приложение к газете "Первое сентября" - №7 - 1994
6. Пичугин Л.Ф. За страницами учебника алгебры: Книга для учащихся 7-9 кл. средней школы. – М.: Просвещение, 1990.

Ресурсы Интернета:

1. http://wikipedia.org 
2. Портал Естественных наук http://e-science.ru/forum/index.php?s=80eab7d3816a082e5ee44635ec2548968showtopic=125068st=80 
3. http://www.natalimak1.narod.ru/prost.htm