Исследовательская работа «Об одном видоизменении способа, известного под названием Эратосфенова решета»

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











На снимке
скульптура абстрактного экспрессиониста
Марка Ди Суверо «Решето Эратосфена»,
установленная в кампусе
Стэнфорского университета


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





Работу выполнил
ученица 8Б класса
Ермилова Алиса
научный руководитель
Ларионова Вера Ивановна


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


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

Содержание

стр.

1
Введение..
3

2
Теоретическая часть



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


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

3
Практическая часть
Еще раз о поиске простых чисел.................................................

10 - 12

4
Заключение......
13


Литература..
13


1. ВВЕДЕНИЕ
Актуальность
В 8 классе мы изучали тему «Квадратные корни». В одном из заданий на данную тему необходимо было вынести множитель из-под знака корня 13 QUOTE 1415. Конечно, данную задачу в лоб мне решить не удалось. Мне необходимо было разложить число 9648 на простые множители.
9648
2

4924
2

2412
2

1206
2

603
3

201
3

67
?


Но, оказалось, что сделать это было не так уж просто. При разложении числа 9648 на простые множители мне необходимо узнать, является число 67 простым или составным. Но под рукой у меня не оказалось таблицы простых чисел. Поэтому мне пришлось воспользоваться известным методом нахождения простых чисел – "Решето Эратосфена". Но это у меня заняло много времени. Поэтому возникла проблема, которую я хочу решить в ходе работы: выяснить, решето Эратосфена – единственный способ нахождения простых чисел или есть еще способ?
Таким образом, объектом моего исследования являются простые числа, а предметом исследования – способ нахождения простых чисел.
Предположу гипотезу, что существует еще способ нахождения простых чисел, отличный от решета Эратосфена. Тогда я хочу поставить перед собой следующую цель исследования: если существует еще способ нахождения простых чисел, то исследовать его алгоритм и использовать при решении задач.
Для достижения своей цели я должна решить следующие задачи:
1. Систематизировать знания по теме: "Простые и составные числа";
2. Исследовать закономерности расположения простых и составных чисел.
3. Привести способы нахождения простых чисел.
Методы исследования:
обработка и анализ научно-публицистических и учебных изданий по исследуемой проблеме;
метод сравнения и сопоставления полученных фактов.
2. ТЕОРЕТИЧЕСКАЯ ЧАСТЬ
2.1. Немного о простых числах
Сразу замечу, что простые числа принадлежат множеству натуральных чисел. Евклид определял простые числа так: "Простое число есть измеряемое только единицей”. Иными словами, простое число это натуральное число, которое имеет ровно два различных натуральных делителя: единицу и самого себя. Все остальные числа, кроме единицы, называются составными. Таким образом, все натуральные числа, бо
·льшие единицы, разбиваются на простые и составные. Число 1 (единица) не причисляется ни к простым, ни к составным числам.
Для начала приведу ряд простых чисел в интервале (1, 500). Сделаю это в форме таблицы, чтобы лучше увидеть, как распределяются простые числа в  ряду натуральных чисел (табл.1). Ячейки, содержащие простые числа, выделены темным цветом.

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

Промежуток натурального ряда
Простых чисел в этом промежутке

От 1 до 10
4

От 10 до20
4

От 20 до 30
2

От 30 до 40
2

От 40 до 50
3

От 50 до 60
2

От 60 до 70
2

От 70 до 80
3

От 80 до 90
2

От 90 до 100
1


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

Промежуток натурального ряда
Простых чисел в этом промежутке

От 100 до 200
21

От 200 до 300
16

От 300 до 400
16

От 400 до 500
17

От 500 до 600
14

От 600 до 700
16

От 700 до 800
14

От 800 до 900
15

От 900 до 1000
14


табл.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:
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


Теперь покажу, как выглядит список после вычёркивания всех чисел кратных 3:
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






Теперь закрасим числа, кратные 5
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


Осталось вычеркнуть числа кратные 7
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


В этом примере процедура отсеивания (зачёркивания) завершилась на простом числе 7, то есть последний раз мы зачёркивали в этом списке каждое седьмое число, следующее за числом 7. Числа кратные 11 мы уже не будем зачёркивать (отсеивать), так как это число больше квадратного корня из 50.
Окончательно получим простые числа. Они оказались в таблице незакрашенными, кроме 1.
Во времена Эратосфена писали на восковых дощечках, а вместо того, чтобы числа зачёркивать, дощечку в нужном месте прокалывали. Отсюда и произошло название способа – "решето Эратосфена”: составные числа как бы "просеивались” в проколотые дырки, а простые числа оставались в "решете”. Поэтому такой способ составления таблицы простых чисел получил название «решета Эратосфена».
Определенный интерес представляет статья Буняковского «Об одном видоизменении способа, известного под названием Эратосфенова решета» (1882г.). В отличие от Эратосфена Буняковский выделяет из последовательности испытуемых чисел простые числа, рассматривая отдельно числа, оканчивающиеся на 1, на 3, на 7, на 9, и используя при этом решения вспомогательных неопределенных уравнений первой степени (довольно простого вида). Я не разбиралась с этим приемом. Предоставляю данный метод читателям для самостоятельного изучения. В помощь даю ссылку на форум "[ Cкачайте файл, чтобы посмотреть ссылку ]” в списке литературы.
В настоящее время составлены таблицы простых чисел, простирающиеся до миллионов.

ПРАКТИЧЕСКАЯ ЧАСТЬ
Еще раз о поиске простых чисел
Выпишу числа по 10 в строке и в ней закрашу простые числа.

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

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

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
122
123
124
125
126
127
128
129
130

131
132
133
134
135
136
137
138
139
140

141
142
143
144
145
146
147
148
149
150

151
152
153
154
155
156
157
158
159
160

161
162
163
164
165
166
167
168
169
170

171
172
173
174
175
176
177
178
179
180

181
182
183
184
185
186
187
188
189
190

191
192
193
194
195
196
197
198
199
200


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

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

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


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

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

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

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








13 PAGE \* MERGEFORMAT 141015






Рисунок 1Рис. 115