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

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

Вот таким же примерно способом отделяют и простые числа от составных.
Требуется, предположим, выделить все простые числа в пределах от 2 до некоторого данного целого числа N. Выпишем сначала подряд все целые числа от 2 до N:
2, 3, 4, 5…..N. Первое простое число 2. Подчеркнем его, а все числа, кратные двум (четные), зачеркнем. Первое из оставшихся чисел 3. Подчеркнем его как простое, а все числа «через два на третье» (то-есть кратные трем) зачеркнем. Первое число из оставшихся теперь 5 (число 4 уже зачеркнуто). Подчеркиваем его как простое и зачеркиваем все числа «через четыре на пятое» (то-есть кратные пяти) и так далее.
Все подчеркнутые числа и образуют таблицу простых чисел в пределах от 2 до N:
1231
Такой способ постепенного «просеивания» чисел был придуман более чем 2000 лет назад греческим математиком Эратосфеном (276—196 гг. до н. э.). Эратосфен не зачеркивал числа, кратные 2, 3, 5 и т. д., а прокалывал дырочки над ними. Получалось нечто вроде решета, сквозь отверстия которого как бы просеивались составные числа, а простые оставались. Так до сих пор этот способ получения таблицы простых чисел и называется эратосфено-вым решетом.

Способ, как видите, очень кропотливый, но вполне надежный.

Коллективными усилиями таблица простых чисел в настоящее время доведена до 10 миллионов, то-есть имеется таблица всех простых чисел от 1 до 10000000. За пределами этой таблицы известны только отдельные простые числа. Так, например, математик-самоучка И. М. Первушин в 1883 г. доказал, что число

2^61 — 1=2 305 843 009 213 693951

есть число простое.

Длительное время число

2^127—1 = 170 141 183460 469231 731 687 303715884 105 727

было наибольшим известным простым числом. При помощи современных быстродействующих вычислительных машин в Лос-Анжелосе было получено еще большее простое число:

2^2281— 1.

В настоящее время это число и является наибольшим из известных простых чисел.

И. М. Первушин, кроме того, доказал, что составным является число 2^2 + 1, так как оно делится на 167 772161. Число 2а2> содержит 2525 223 цифры… Результаты Первушина были проверены в Петербургской и Парижской академиях наук и подтверждены.

Очень кропотливую работу по установлению делителей больших чисел вида 2Р + 1 проделал в недавнее время М. И. Слободской, будучи еще студентом Грозненского педагогического института. Он самостоятельно нашел и доказал интересную теорему, позволяющую сразу находить делитель числа 2Р — 1 для разнообразных значений числа р. Например он показал, в частности, что число 2^5002331 — 1, содержащее свыше полутора миллионов цифр, делится на число 10004663*).

Математики, конечно, не могли мириться с тем, что простые числа добываются кустарными способами. Им, естественно, хотелось создать такую общую формулу, которая в зависимости от всевозможных целых значений величины п давала бы только простые числа. Но, увы, такая формула оказалась «синей птицей». Ее никто так и не поймал до сих пор.



Это не спам.

 

На нашем сайте собраны задачи занимательной арифметики, математики, геометрии;
задачи на смекалку и логику, головоломки, логические загадки, игры, ребусы и многое другое
2017 © Самый умный - математическая смекалка