|
Название публикации:
«ПРОСТЫЕ И СОСТАВНЫЕ ЧИСЛА»
Всякий, кто изучает простые числа, бывает очарован и одновременно
ощущает собственное бессилие. Определение простых чисел так просто и
очевидно; найти очередное простое число так легко; разложение на простые
сомножители – такое естественное действие. Почему же простые числа столь
упорно сопротивляются нашим попыткам постичь порядок и закономерности их
расположения? Может быть, в них вообще нет порядка, или же мы так слепы,
что не видим его?
Число – самое главное понятие математики, позволяющее выразить результаты
счёта или измерения.
Понятия простые числа и составные числа относятся к целым положительным
числам, которые больше единицы. Такие целые числа, в зависимости от
количества их положительных делителей, подразделяются на простые и
составные числа.
Древнегреческих ученых заинтересовало: сколько может быть простых чисел в
натуральном ряду? Ответил на этот вопрос Евклид, доказав, что простых чисел
бесконечное множество.
Простые числа – это целые числа, которые имеют только два положительных
делителя, а именно делятся на самих себя и на 1.
Например: 2=2×1, 17=1×17, 29=1×29…
727
Составные числа – это целые числа, которые имеют более двух положительных
делителей.
Например: 24 делится на: 1,2,3,4,6,8,12,24
Отыскание простых чисел является сложной задачей математики. Ученые на
протяжении многих веков пытаются найти формулу, которая позволила бы из
множества натуральных чисел выписать простые.
Эратосфен Киренский
Первый, кто занимался этой задачей, был великий математик
древности Эратосфен, живший почти 2 300 лет назад. Эратосфен
был главным библиотекарь знаменитой Александрийской
библиотеки, математиком, географом, историком, астрономом,
философом и поэтом.
Для отыскания простых чисел греческий математик Эратосфен придумал такой
способ. Он записал все числа от одного до какого - то числа, а потом вычеркнул
единицу, которая не является ни простым, ни составным числом, затем
вычеркивал через одно все числа, идущие после 2(4,6,8 и т.д.). Первым
оставшимся числом после 2 было 3. Далее вычеркивались числа, идущие после
3, но через два числа (числа, кратные 3, т.е. 6,9,12 и т.д.), в конце концов
оставались не вычеркнутыми только простые числа. Такой способ мы называем
«решето Эратосфена».
«Решето Эратосфена» является удобным способом для составления таблицы
простых чисел. Присутствующее в названии слово «решето» не случайно, так как
действия этого метода помогают как бы «просеять» сквозь решето Эратосфена
целые числа, большие единицы, чтобы отделить простые от составных.
Покажем решето Эратосфена в действии при составлении таблицы простых
чисел до 50.
728
Сначала записываем по порядку числа 2, 3, 4, …, 50.
Первое
записанное
число 2 является
простым.
Теперь
от
числа 2 последовательно перемещаемся вправо на два числа и зачеркиваем эти
числа, пока не доберемся до конца составляемой таблицы чисел. Так будут
вычеркнуты все числа, кратные двум.
Первым следующим за 2 невычеркнутым числом является 3. Это число простое.
Теперь от числа 3 последовательно перемещаемся вправо на три числа (учитывая
и уже зачеркнутые числа) и вычеркиваем их. Так будут вычеркнуты все числа,
кратные трем.
Первым следующим за 3 невычеркнутым числом является 5. Это число простое.
Теперь от числа 5 последовательно перемещаемся вправо на 5 чисел (учитываем
729
и зачеркнутые ранее числа) и вычеркиваем их. Так будут вычеркнуты все числа,
кратные пяти.
Дальше вычеркиваем числа, кратные 7, затем, кратные 11 и так далее. Процесс
заканчивается, когда не останется чисел для вычеркивания. Ниже показана
законченная таблица простых чисел до 50, полученная с помощью решета
Эратосфена. Все незачеркнутые числа являются простыми, а все зачеркнутые
числа – составными.
Алгоритм проверки числа на простоту
Для того, чтобы проверить, является ли число простым, необязательно
проверять, что оно не делится ни на одно число меньше его. Достаточно
проверить, что число не делится ни на одно из простых чисел, квадрат которых
не превосходит рассматриваемое число.
Предположим, что число n- составное, тогда оно представимо в виде n=ab, где
a>1, b>1. Предположим, что а≤b, то n=ab≥a2, т.е. а≤√n. Следовательно, для
любого простого делителя р числа а выполняется р≤а≤√n. Значит, если число
составное, то у него есть простой делитель не превосходящий √n.
730
Список литературы:
1. Виленкин Н.Я. и др. Математика. 6 класс: учебник для общеобразовательных
учреждений.
2. Виноградов И.М. Основы теории чисел.
3. Михелович Ш.Х. Теория чисел.
4. Куликов Л.Я. и др. Сборник задач по алгебре и теории чисел: Учебное пособие
для студентов физ.-мат. специальностей педагогических институтов.
731
Do'stlaringiz bilan baham: |
