Что такое простые числа и как их найти
. Таблица четных и нечетных простых чисел до 1000
Один из способов нахождения простых чисел — пробное деление
Греческий математик Евклид в III веке до н.э. в девятой книге «Начала» доказал, что простых чисел бесконечно много [1]. РБК Life рассказывает, что такое простые числа, как их определить и чем они отличаются от составных.
Что такое простые числа
Простое число — это натуральное число, которое больше единицы и не имеет натуральных делителей, кроме 1 и самого себя [2]. От составных простые отличаются тем, что имеют только два делителя. Например, 5 — это простое число, так как имеет всего два делителя — 1 и 5. В отличие от него число 6 будет составным, поскольку его можно поделить без остатка не только на 1 и 6, но еще на 2 и 3.
Простые числа имеют большое значение в разных областях, в первую очередь в программировании и шифровании.
Примеры простых чисел
2, 3, 5, 7, 11, 13, 17, 19 … — все это простые числа. 2 — наименьшее простое число. 1 не относится ни к простым, ни к составным числам, поскольку имеет только один делитель — само себя. Последовательность простых чисел никогда не заканчивается, то есть простых чисел бесконечное множество.
Как определить простые числа
Чтобы понимать, какие числа относятся к простым, а какие нет, нужно знать признаки простых чисел, уметь подбирать к ним делители и пользоваться алгоритмом Эратосфена.
Признаки
Как правило, простые числа оканчиваются на 1, 3, 7 или 9. Например, 71, 163, 457 и 619 — это простые числа. Но есть исключения: к простым числам не относятся 21, 27, 33, 39 и другие — это составные числа, так как они имеют более одного делителя. Поэтому важно знать и другие способы по определению простых чисел.
Подбор делителей
Один из способов нахождения простых чисел — пробное деление.
Чтобы выяснить, является ли многозначное число простым или составным, надо хорошо знать признаки делимости чисел и таблицу умножения. Если данное число ни на какое другое, кроме единицы и самого числа, больше не делится, значит, оно относится к множеству простых чисел.
Чтобы выполнить пробное деление, нужно поделить проверяемое число на все простые числа от 2 до квадратного корня из этого числа.
Пример 1. Нужно выяснить, является ли простым число 49. Корень из 49 — это 7. Следовательно, 49 надо разделить на все простые числа до 7 включительно: на 2, 3, 5 и 7. Без остатка 49 делится только на 7. Таким образом, оно имеет более двух делителей: 1, 7 и 49. Значит, это составное число.
Пример 2. Нужно выяснить, является ли простым число 37. Корень из 37 — около 6 (так как корень из 36 будет 6). Значит, 37 надо поделить на 2, 3 и 5. Без остатка оно не делится, следовательно, имеет только два делителя — 1 и 37. Поэтому 37 — простое число.
Решето Эратосфена
Решето Эратосфена — это алгоритм по нахождению простых чисел, разработанный греческим математиком Эратосфеном [3].
- Запишите все числа от 2 до N (где N — это верхняя граница, до которой вы ищете простые числа).
- Начните с первого числа (2). Это первое простое число.
- Вычеркните все числа, кратные 2 (то есть 4, 6, 8, 10…), так как они не являются простыми.
- Перейдите к следующему незачеркнутому числу (это будет 3). Это следующее простое число.
- Вычеркните все числа, кратные 3 (6, 9, 12, 15…), если они еще не вычеркнуты.
- Повторите процесс: переходите к следующему незачеркнутому числу, объявите его простым и вычеркните все его кратные.
- Остановитесь, когда дойдете до числа, которое больше √N (квадратного корня из N).
- Все оставшиеся незачеркнутые числа будут простыми.
Таблица простых чисел до 1000
Примеры простых чисел
Интересные факты о простых числах
Почему 1 не простое число
Чтобы ответить на этот вопрос, давайте сначала определим, что такое простое число. Простое число — это натуральное число, имеющее два различных натуральных делителя — единицу и само себя. Например, число 3 делится на 1 и 3. А у 1 только один делитель — сама единица, поэтому ее не относят к простым числам.
Самое большое простое число
Поиск «больших» простых чисел уже много веков занимает умы математиков. В действительности найти такие числа непросто, поэтому за открытие больших простых чисел дают награды. Например, в августе 2008 года в рамках проекта GIPMS было обнаружено простое число, которое содержит 12 978 189 десятичных цифр, за что проект получил премию в размере $100 тыс. А самое большое известное простое число — это число 2^136 279 841-1. Его открыл совсем недавно — 12 октября 2024 года — Люк Дюрант в рамках того же проекта. Найденное простое число содержит невероятных 41 024 320 десятичных цифр.
Сколько существует четных простых чисел
Число 2 — единственное четное простое число. Оно также является наименьшим простым числом. Следующее четное число — 4. Оно уже составное, так как делится на 1, 2 и 4, то есть имеет более двух делителей.
