Студопедия
Случайная страница | ТОМ-1 | ТОМ-2 | ТОМ-3
АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатика
ИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханика
ОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторика
СоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансы
ХимияЧерчениеЭкологияЭкономикаЭлектроника

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

Читайте также:
  1. Вы должны уметь различать и "быть как решето": нужная информация остается в голове, а ненужная вылетает из нее.
  2. Подсевное решето В
  3. Центрально-сжатые сквозные колонны. Типы сечений. Типы решеток. Влияние решеток на устойчивость стержня сквозной колонны.

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

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

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


Дата добавления: 2015-07-18; просмотров: 219 | Нарушение авторских прав


Читайте в этой же книге: Понятие числа | Действия над натуральными числами – мерами величин | Выбора действий и наглядной иллюстрацией условия задачи | Позиционные системы счисления | Перевод натуральных чисел из одной позиционной системы счисления в другую | Восьмеричная система счисления | Компьютеры и системы счисления | Отношение делимости и его свойства | Признаки делимости на 2 и 5. | Признаки делимости в других позиционных системах счисления |
<== предыдущая страница | следующая страница ==>
Четыре класса целых неотрицательных чисел.Простые и составные числа| Некоторые теоремы, предшествующие основной теореме арифметики

mybiblioteka.su - 2015-2024 год. (0.006 сек.)