Сообщение по теме "Простые числа"

4

6

8

12

4

6

8

9

10

12,

14

15

Эти непростые «простые числа»

Всякий, кто изучает простые числа, бывает очарован и одновременно ощущает собственное бессилие. Определение простых чисел так просто и очевидно; очередное простое число так легко; разложение на простые сомножители - такое естественное действие. Почему же простые числа столь упорно сопротивляются нашим попыткам постичь порядок и закономерности их расположения? Может быть, в них вообще нет порядка, или же мы так слепы, что не видим его?

Ч. Узерелл «Этюды для программистов»

Какие числа называются простыми? Так ли они просты на самом деле? Простые числа с давних времен привлекают внимание математиков. Простые числа следуют одно за другим по закону, который еще не найден. Хорошо было бы, если все простые числа можно было сосчитать! Но эта проблема до сих пор остается нерешенной.

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

Простое число— это натуральное число, которое имеет ровно 2 натуральных делителя (только 1 и самого себя).

Составное число— натуральное число большее 1, не являющееся простым.1(единица) – особое число, оно не является ни простым, ни составным. Таким образом, все натуральные числа, за исключением единицы, разбиваются на простые и составные.

Евклид — древнегреческий математик, автор первого из дошедших до нас теоретических трактатов по математике. Биография, сведения о нем крайне скудны. Его научная деятельность протекала в Александрии в 3 веке до н. э. Евклид — первый математик александрийской школы. Его главная работа «Начала» содержит изложение планиметрии, стереометрии и ряда вопросов теории чисел. В ней он подвёл итог предшествующему развитию греческой математики и создал фундамент дальнейшего развития математики. Евклид — автор работ по математике, астрономии, оптике, музыке и др.

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

Эратосфен Киренский —древнегреческий математик (276-194 до нашей эры), заведовал Александрийской библиотекой и заложил основы математической географии, вычислив с большой точностью величину земного шара. Он был первым составителем таблицы простых чисел.

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

Решето́ Эратосфе́на — алгоритм нахождения всех простых чисел до некоторого целого числа n. Как и во многих случаях, здесь название алгоритма говорит о принципе его работы, то есть решето подразумевает фильтрацию, в данном случае фильтрацию всех чисел за исключением простых. По мере прохождения списка нужные числа остаются, а ненужные исключаются.
Алгоритм «Решето Эратосфена»

Эратосфен родился в 276 году до нашей эры, то есть этому методу уже около 2200 лет. Но он настолько прост и изящен,что можно объяснить его любому ребёнку. Итак, в чем суть метода и как его применять.

Предположим для примера,что нужно вычислить все простые числа меньшие 40.

Берем числовую последовательность натуральных чисел, начиная с 2

2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12

И удаляем все числа кратные 2.

Для этого умножаем числа натурального ряда, по порядку на 2 и результат

умножения вычеркиваем.

2×2=4, вычеркиваем 4,

2х3=6, вычеркиваем 6 и т.д.

Таким образом, исключаем все четные, больше 2.

Два — простое число, так как имеет, всего два натуральных делителя 1 и 2.

Получаем.

2, 3,,5,,7,,9,10,11,…

Затем вычеркиваем числа кратные трем (умножаем на 3 все числа, также по

порядку ):

2, 3,5,,7,,,,11,13,,…

Потом, вычеркиваем числа кратные пяти и т.д.

В итоге получим последовательность не зачеркнутых чисел, которые и

есть простые.

Сам Эратосфен построил таблицу простых чисел до 1000.

Сейчас, найдены огромные простые числа, но процесс все еще идет.

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

Согласно теореме Евклида, количество простых чисел бесконечно. Следовательно, количество простых чисел, превышающих наибольшее известное, тоже бесконечно. Представим, что количество простых чисел конечно. Перемножим их и прибавим единицу. Полученное число не делится ни на одно из конечного набора простых чисел, потому что остаток от деления на любое из них даёт единицу. Значит, число должно делиться на некоторое простое число, не включённое в этот набор.

Многие учёные-математики, а также любители, занимаются поиском рекордных Electronic Frontier Foundationх по величине простых чисел, за нахождение которых организацией было предложено несколько наград в зависимости от величины числа. Так, в 2009 году была вручена премия в 100000долларов США, назначенная сообществом ElectronicFrontierFoundation за нахождение простого числа, десятичная запись которого содержит не менее 10 миллионов цифр.