Проверка простого числа

Проверка Простого Числа: Полное Руководство

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

Что Такое Простое Число?

Простое число — это натуральное число, большее единицы, которое делится без остатка только на единицу и на само себя. Иными словами, у простого числа ровно два натуральных делителя.

Примеры простых чисел: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 97, 101, 9973.

Составное число — это натуральное число, большее единицы, у которого есть хотя бы один делитель, отличный от единицы и самого числа. Иными словами, составное число можно разложить в произведение двух меньших натуральных чисел, каждое из которых больше единицы.

Примеры составных чисел: 4 = 2 × 2, 6 = 2 × 3, 91 = 7 × 13, 561 = 3 × 11 × 17.

Простое и Составное: В Чём Разница

Ключевое отличие лежит в количестве делителей. У простого числа их ровно два, у составного — три и больше. Это различие удобно проверять вручную для небольших чисел.

Число	Делители	Количество делителей	Тип
1	1	1	Особый случай
2	1, 2	2	Простое
7	1, 7	2	Простое
9	1, 3, 9	3	Составное
12	1, 2, 3, 4, 6, 12	6	Составное
91	1, 7, 13, 91	4	Составное
97	1, 97	2	Простое

Почему 1 — Не Простое Число?

Многие интуитивно считают единицу простым числом — ведь она делится только на единицу и на саму себя. Но определение требует, чтобы число было больше единицы. Причина глубже, чем формальность: если бы 1 считалась простой, основная теорема арифметики перестала бы работать.

Основная теорема арифметики утверждает, что любое натуральное число больше единицы раскладывается на простые множители единственным способом с точностью до порядка множителей. Если бы 1 была простой, число 6 можно было бы записать как 2 × 3, или 1 × 2 × 3, или 1 × 1 × 2 × 3 — и единственность исчезла бы. Поэтому математики договорились: единица не является ни простой, ни составной.

Число 0 тоже не является ни простым, ни составным. Ноль делится на любое натуральное число, поэтому у него бесконечно много делителей, что не подходит ни под одно из определений. Отрицательные числа в теории простых чисел вообще не рассматриваются: простые числа — это элементы множества натуральных чисел.

Как Проверить, Простое Ли Число: Метод Перебора Делителей

Самый простой и наглядный способ проверки — перебор делителей. Алгоритм состоит из четырёх шагов:

1. Проверьте особые случаи. Если число меньше 2, оно не является ни простым, ни составным. Если число равно 2 или 3, оно простое.
2. Проверьте делимость на 2. Если число чётное, оно составное (кроме самой двойки).
3. Переберите нечётные делители от 3 до квадратного корня из числа. Если хотя бы один делит число без остатка — число составное.
4. Сделайте вывод. Если ни один делитель не подошёл, число простое.

Почему Достаточно Проверять Делители До √n

Это ключевая идея, которая превращает проверку из долгого перебора в быстрый процесс. Доказывается она в две строки.

Предположим, что число n составное. Значит, его можно представить в виде произведения n = a × b, где a и b — натуральные числа, большие единицы. Допустим, что оба множителя больше √n. Тогда их произведение было бы больше, чем √n × √n = n, что противоречит условию a × b = n. Значит, хотя бы один из множителей не превосходит √n.

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

Пример 1: Проверяем Число 91

Пример 2: Проверяем Число 561

Пример 3: Проверяем Число 9973

Быстрые Признаки Делимости

Прежде чем запускать полный перебор, полезно отсеять очевидные случаи. Эти правила экономят время и позволяют быстро определить, что число составное:

• На 2: число оканчивается на чётную цифру (0, 2, 4, 6, 8).
• На 3: сумма цифр числа делится на 3.
• На 5: число оканчивается на 0 или 5.
• На 7: удвоенную последнюю цифру вычитают из числа без последней цифры; если результат делится на 7, делится и исходное число.
• На 11: разность суммы цифр на нечётных и чётных позициях делится на 11.

Любой из этих признаков, сработавший положительно, немедленно доказывает, что число составное. Если ни один не сработал — это ещё не значит, что число простое: нужно продолжать перебор.

Решето Эратосфена: Поиск Всех Простых Чисел Сразу

Если нужно найти не одно простое число, а все простые числа до некоторого предела, удобнее использовать решето Эратосфена. Это древний алгоритм, придуманный ещё в III веке до нашей эры.

1. Выпишите все числа от 2 до N.
2. Первое непомеченное число — 2 — простое. Вычеркните все числа, кратные 2 (4, 6, 8, 10, …).
3. Следующее непомеченное число — 3 — простое. Вычеркните все числа, кратные 3 (6, 9, 12, …).
4. Следующее — 5, затем 7, 11 и так далее.
5. Остановитесь, когда очередное найденное простое число превысит √N. Все оставшиеся непомеченные числа — простые.

Решето эффективно для диапазонов до нескольких миллионов: оно работает за время, близкое к линейному, и не требует проверять каждое число отдельно.

Таблица Простых Чисел До 100

Эти 25 чисел стоит помнить наизусть — они постоянно встречаются в задачах на разложение и сокращение дробей.

Разложение на Простые Множители

Когда число оказалось составным, естественный следующий шаг — разложить его на простые множители. Делается это последовательным делением на наименьший найденный простой делитель.

Основная теорема арифметики гарантирует, что такое разложение единственно. Именно поэтому простые числа называют «атомами» арифметики: из них собираются все остальные числа, и собираются всегда одинаково.

Где Это Применяется на Практике

• Криптография. Алгоритм RSA, защищающий банковские транзакции и переписку, основан на том, что перемножить два больших простых числа легко, а разложить результат обратно — практически невозможно.
• Сокращение дробей. Чтобы привести дробь к несократимому виду, нужно найти общие простые множители числителя и знаменателя.
• Нахождение НОК и НОД. Оба вычисляются через разложение на простые множители.
• Программирование. Хеш-таблицы, генераторы псевдослучайных чисел и алгоритмы шифрования активно используют простые числа.
• Олимпиадная математика. Задачи на делимость, остатки и сравнения почти всегда опираются на свойства простых чисел.
• Бытовые расчёты. Разделить 91 конфету поровну в несколько пакетов — возможно только если 91 = 7 × 13, то есть на 7 или 13 пакетов.

Типичные Ошибки

• Ошибка 1: считать 1 простым числом. Единица не является ни простой, ни составной. У неё только один делитель.
• Ошибка 2: считать 2 составным, потому что оно чётное. Двойка — единственное чётное простое число.
• Ошибка 3: останавливать перебор слишком рано. Проверив делители до 5, нельзя делать вывод о простоте числа 49.
• Ошибка 4: перебирать делители дальше √n. Это бесполезная работа: если делителя не нашлось до √n, его нет вообще.
• Ошибка 5: проверять только простые делители, забывая про составные. Это не ошибка по сути, но требует знания списка простых чисел. Перебор всех нечётных чисел надёжнее.
• Ошибка 6: доверять быстрым тестам на простоту без проверки. Числа Кармайкла (например, 561) проходят некоторые тесты, оставаясь составными.
• Ошибка 7: путать «не делится на 7» с «простое число». Число может не делиться на 7, но делиться на 13.

Часто Задаваемые Вопросы

Как быстро проверить, простое ли число?
Проверьте делимость на 2, 3 и 5 по признакам делимости. Затем переберите нечётные делители от 7 до √n. Если ни один не подошёл — число простое.

Сколько всего простых чисел?
Бесконечно много. Это доказал ещё Евклид: если предположить, что простых чисел конечное множество, то их произведение плюс единица даст новое число, которое не делится ни на одно из них — противоречие.

Какое самое маленькое простое число?
Двойка. Это единственное чётное простое число.

Является ли 1 простым числом?
Нет. По определению простое число должно быть больше 1. Единица — особый случай, у неё ровно один делитель.

Является ли 0 простым числом?
Нет. Ноль делится на любое натуральное число, поэтому не подходит ни под определение простого, ни под определение составного.

Можно ли проверить простое число без перебора делителей?
Да, существуют вероятностные тесты (Миллера — Рабина, Ферма) и детерминированные тесты (AKS). Они применяются для очень больших чисел в криптографии. Для чисел до 10¹² перебор делителей до √n работает быстрее и проще.

Почему 91 не является простым числом?
Потому что 91 = 7 × 13. У него есть делители 7 и 13 помимо 1 и 91.

Как разложить число на простые множители?
Последовательно делите число на наименьший простой делитель, пока не получите простое число. Например, 84 = 2 × 42 = 2 × 2 × 21 = 2² × 3 × 7.

Заключение

Проверка простого числа — задача, которая выглядит сложной только на первый взгляд. Достаточно запомнить главное правило: перебирать делители нужно только до квадратного корня из числа. Всё, что дальше, — избыточно. Наш калькулятор автоматически выполняет этот перебор, показывает, на каком делителе число «сломалось», строит полное разложение на простые множители и выводит список всех делителей. Используйте его, чтобы проверять домашние задания, готовиться к экзаменам или просто быстро получать ответ — и постепенно вы научитесь определять простые числа в уме.