Если вы ещё не знаете, что такое «Эратосфеново решето», эта статья для вас. Прежде всего вспомним, какие числа называют простыми и составными.
Простое число — это натуральное число, не равное 1, которое делится только на 1 и на само себя. Примеры: 2, 3, 5, 7, 11 и т.д.
Ну а составное число — натуральное, которое имеет делители, отличные от 1 и самого себя. Примеры: 4, 6, 8, 9 и т.д.
С древних времён простые числа привлекали внимание математиков. Древнегреческий математик Евклид, живший за 3 века до н.э. доказал, что простых чисел существует бесконечное множество.
Попробуем составить таблицу простых чисел от 2 до 100. Выпишем их в таблицу. Подчеркнём число 2, а все числа, кратные 2 (через одно), зачеркнём.
Далее, подчеркнём первое из оставшихся чисел (это число 3) и будем зачёркивать числа, кратные трём (через 2 на третье из оставшихся).
Следующее из оставшихся чисел, будет 5, подчёркиваем его, это третье простое число. И зачёркиваем числа, кратные пяти. И так далее…
Вот так этот процесс выглядит в движении:
Получаем таблицу простых чисел в промежутке от 1 до 100 (числа в квадратах):
Этот способ постепенного «просеивания» чисел был придуман более чем 2000 лет назад Эратосфеном — тоже древнегреческим математиком (276-196 гг. до н.э.).
В то время люди писали на дощечках, покрытых воском (по другим данным на папирусе). Эратосфен не зачёркивал числа, кратные 2, 3, 5, … , а прокалывал дырочки на их месте, исключая тем самым составные числа. По окончании дощечка была похожа на решето (сито). Поэтому такой алгоритм составления таблицы простых чисел и назвали «решето Эратосфена».
Замечено, что в начале таблицы простые числа расположены намного гуще, чем, например, вблизи 1000. Так, например, в первом десятке (от 1 до 10) расположено 4 простых числа — 2, 3, 5, 7, т.е 40 %. Первая сотня натуральных чисел содержит 25 простых чисел (25 %), а миллион уже содержит лишь 8 % простых чисел.
А вот как определить, сколько содержится простых чисел в ряду натуральных чисел от 1 до любого числа N?
Вопросом о том, как найти закон, по которому простые числа распределяются в натуральном ряде, занимались многие математики: немец Карл Фридрих Гаусс (1777 - 1885), француз Адриен Мари Лежандр (1752-1833), русский математик Пафнутий Львович Чебышев (1821-1894), немец Бернхард Риман (1826- 1866), француз Жак Адамар (1865-1963), бельгийский математик Шарль Жан де ла Валле-Пуссен (1866-1962), венгерский математик Пал Эрдёш (1913-1996).
Закон распределения простых чисел даёт возможность установить, сколько простых чисел заключается в сколь угодно большом промежутке чисел.
Всё-таки, математика — удивительная наука, здесь столько много интересного!
Автор: Чудневцева Ирина, соавтор канала Хакнем Школа.