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

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

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

Метод Эратосфена заключается в следующем. Сначала выписывают все числа от 2 до n. После этого вычёркивают все числа, кратные 2, кроме самого числа 2. Например, если n = 40, получим:

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

Мы видим, что числа вычёркиваются через одно, причём, все оставшиеся, кроме 2, не делятся на 2, т.е. и наименьший простой делитель наверняка больше 2.

Первым оставшимся числом после 2 является число 3. Вычеркнем все числа, кратные 3, кроме самого числа 3 (т.е. вычёркиваем каждое третье число. Оставшиеся числа не делятся ни на 2, ни на 3 (кроме 2 и 3), получим:

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

На следующем шаге вычёркиваем числа кратные 5, кроме числа 5. (Это первое число, оставшееся после вычёркивания и идущее после чисел 2 и 3), получим:

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

Числа, оставшиеся после трёх вычеркиваний (кроме самих 2, 3, 5), не делятся ни на 2, ни на 3, ни на 5, т.е. их простые делители должны быть, по крайней мере, равны 7. Но наименьший простой делитель числа меньшего 40 не превосходит , т.е. меньше 7. Значит, среди оставшихся чисел нет составных, все они простые.

Итак, простые числа, меньшие 40 – это 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37.

Отсюда, как следствие, вытекают правила:

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

Так, чтобы составить таблицу простых чисел, не больших 100, надо вычеркнуть на отрезке натурального ряда от 2 до 100 все составные числа кратные простым не большим = 10, т.е. кратные простым 2, 3, 5, 7. Простых чисел, меньших 100, будет 25, это

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.

Правило 2. Чтобы определить простым или составным является натуральное число m, надо делить это число на простые числа 2, 3, 5, … не большие , если m делится хотя бы на одно из этих простых чисел, то оно составное, если не делится, то простое.

П р и м е р. Установить, является ли число 1973 простым или составным. Для этого надо испытать делимость 1973 на простые числа, не большие » 44. Следовательно, надо испытать делимость на 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43. Испытания показывают, что число 1973 простое.

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

С помощью готовой таблицы решается вопрос о том, является ли данное число простым или составным. Хотя и было доказано, что наибольшего простого числа не существует, математики стремятся обнаружить большие простые числа, далеко выходящие за пределы даже самых больших таблиц. Одно из таких больших простых чисел равно 2³²¹⁷ – 1. Это число в десятичной записи имеет 969 цифр. То, что число простое, было установлено в 1957 году с помощью ЭВМ.

Среди простых чисел есть много таких, разность которых равна 2. Например, пары простых чисел 3 и 5, 5 и 7, 11 и 13, 17 и 19 и т.д. Такие пары простых чисел называют числами-близнецами. Числа – близнецы встречаются на протяжении всей исследованнойчасти натурального ряда. Известны весьма большие числа-близнецы, например, 100116957 и 100116959. Однако до сих пор не решен вопрос о том, существует бесконечное или конечное множество пар чисел-близнецов.

Дата добавления: 2015-07-18