Проверка числа на простоту
Введите любое целое число до одного триллиона и мгновенно узнайте, простое оно или составное. Калькулятор также покажет наименьший простой делитель и полное разложение на простые множители с пояснениями.
Простое ли это число?
Формула проверки числа на простоту
Где:
- \(n\) — проверяемое целое число
- \(d\) — возможный делитель
- \(\sqrt{n}\) — квадратный корень из \(n\), округлённый вниз до целого
Формула описывает метод перебора делителей: достаточно искать делители только до \(\sqrt{n}\), потому что если \(n = a \times b\) и оба множителя больше 1, то хотя бы один из них не превосходит \(\sqrt{n}\). Именно поэтому калькулятор проверяет кандидатов лишь до квадратного корня, пропуская числа, кратные 2 и 3 (сначала проверяются 2 и 3, а затем числа вида \(6k \pm 1\)).
Проверка числа на простоту — пример расчёта
Пример: простое ли число 91? Проверяем делители до \(\sqrt{91} \approx 9.54\), то есть только 2, 3, 5 и 7.
\[ 91 \div 2 = 45.5 \quad (\text{не делитель}) \]
\[ 91 \div 3 = 30.\overline{3} \quad (\text{не делитель}) \]
\[ 91 \div 5 = 18.2 \quad (\text{не делитель}) \]
\[ 91 \div 7 = 13 \quad (\text{делится нацело — 7 является делителем!}) \]
Результат: 91 — составное число. Его наименьший простой делитель — 7, поскольку \(91 = 7 \times 13\), а полное разложение на простые множители: \(91 = 7 \times 13\).
Как пользоваться калькулятором
- Введите проверяемое целое число в поле Число для проверки (n). Подойдёт любое целое число от 0 до 1 000 000 000 000 (1012).
- Посмотрите строку Результат — простое или составное. Для чисел меньше 2 будет указано, что число не является ни простым, ни составным.
- Если число составное, обратите внимание на поле Простой делитель (показывается для составных чисел) — это наименьшее простое число, на которое делится ваше число, вместе со вторым множителем.
- Прочитайте раздел Полное разложение на простые множители с пояснением: в нём число раскладывается на простые множители и объясняется, как был получен ответ.
Что такое простое число?
Простое число — это целое число больше 1, которое имеет ровно два натуральных делителя: 1 и само себя. Первые простые числа: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29. Все остальные целые числа больше 1 — составные: их можно представить в виде произведения двух меньших целых чисел, каждое из которых больше 1.
Особого упоминания заслуживает число 2: это единственное чётное простое число, ведь любое другое чётное число делится на 2. Числа 0 и 1 не являются ни простыми, ни составными: у 1 только один делитель, а 0 делится на любое натуральное число, поэтому оба не подходят под определение «ровно два делителя».
Простые числа — это «кирпичики», из которых строится арифметика. Основная теорема арифметики гласит, что каждое целое число больше 1 раскладывается на простые множители единственным образом (если не учитывать порядок множителей). Поэтому калькулятор и показывает полное разложение для составных чисел: оно точно показывает, из каких простых «кирпичиков» состоит ваше число и сколько раз каждый из них встречается.
Истолковать результат несложно. Если вердикт — простое, число нельзя разложить дальше. Если составное — показанный наименьший простой делитель служит простейшим доказательством: при делении на него вашего числа получается целое, а значит, число заведомо не простое.
Ограничения, допущения и полезные советы
- Диапазон: калькулятор принимает целые числа от 0 до 1012. Для бо́льших чисел нужны более сложные методы.
- Метод: используется перебор делителей с оптимизацией \(6k \pm 1\) — он быстрый и даёт математически точный ответ для чисел в поддерживаемом диапазоне. Для астрономически больших чисел вместо него применяют вероятностные тесты, например основанные на малой теореме Ферма: перебор делителей точен, но становится слишком медленным.
- Дроби и отрицательные числа: простота определена только для целых чисел больше 1, поэтому для дробных, отрицательных чисел, а также для 0 и 1 калькулятор выдаёт пояснение вместо вердикта.
- Быстрая проверка в уме: прежде чем открывать калькулятор, простоту часто можно отвергнуть устно — число, оканчивающееся на 0, 2, 4, 5, 6 или 8, делится на 2 или 5, а число, сумма цифр которого кратна 3 (как у 91: 9 + 1 = 10… впрочем, 10 не делится на 3, так что здесь этот признак не помогает), делится на 3. Признак по сумме цифр связан с цифровым корнем.
- Зачем нужно разложение: разложение на простые множители лежит в основе многих инструментов теории чисел — от мультипликативно обратного элемента по модулю n, применяемого в криптографии, до решения систем сравнений с помощью китайской теоремы об остатках.
Часто задаваемые вопросы
Как проверить, простое ли число, вручную?
Проверьте, делится ли ваше число нацело хотя бы на одно целое число от 2 до \(\sqrt{n}\). Если нет — число простое. Для 137 имеем \(\sqrt{137} \approx 11.7\), поэтому достаточно проверить 2, 3, 5, 7 и 11 — ни одно из них не делит 137, значит, 137 простое. После проверки 2 пропускайте чётные кандидаты — это экономит время. И помните: выходить за пределы квадратного корня никогда не нужно.
Почему 1 — не простое число?
У простого числа должно быть ровно два натуральных делителя: 1 и оно само. У единицы делитель только один, поэтому под определение она не подходит. Это соглашение к тому же сохраняет справедливость основной теоремы арифметики — если бы 1 считалась простой, каждое число больше 1 имело бы бесконечно много разложений вроде \(6 = 2 \times 3 = 2 \times 3 \times 1\). Так что 1 — ни простое, ни составное число.
Какие признаки делимости помогают быстрее всего до начала проверки?
Посмотрите на последнюю цифру: числа, оканчивающиеся на 0, 2, 4, 5, 6 или 8, делятся на 2 или 5. Сложите цифры — если сумма делится на 3, то и число делится (для 87: \(8 + 7 = 15\), делится на 3, значит, 87 составное). Для 11 попеременно складывайте и вычитайте цифры: если результат делится на 11, то и само число делится. Эти правила мгновенно отсекают большинство составных чисел.
В чём разница между простыми и взаимно простыми числами?
Простота — свойство одного числа: у него ровно два делителя. Взаимная простота — свойство пары: два числа взаимно просты, если их наибольший общий делитель равен 1. Например, 8 и 15 оба составные, но взаимно просты, потому что \(\gcd(8, 15) = 1\). Заметьте: 2 и 3 взаимно просты, но и 4 с 9 тоже — сами числа вовсе не обязаны быть простыми.
Какие числа часто кажутся простыми, но не являются?
Знаменитые «псевдопростые» примеры: 91 (\(= 7 \times 13\)), 57 (\(= 3 \times 19\)), 51 (\(= 3 \times 17\)), 87 (\(= 3 \times 29\)) и 119 (\(= 7 \times 17\)). Их упускают, потому что они не делятся ни на 2, ни на 5, ни на «заметный» квадрат. При ручной проверке всегда внимательно проверяйте 3 (по сумме цифр), 7 и 11 — именно они выявляют большинство коварных случаев ниже 150.
Как шаг за шагом разложить число на простые множители?
Последовательно делите на наименьший подходящий простой делитель. Для 360: делим на 2, получаем 180, ещё раз на 2 — 90, ещё раз на 2 — 45; 45 нечётное, поэтому делим на 3 — получаем 15, и ещё раз на 3 — получаем 5. Итого \(360 = 2^3 \times 3^2 \times 5\). Продолжайте, пока остаток сам не станет простым числом. Благодаря основной теореме арифметики каждое такое деление гарантированно найдёт очередной простой множитель.
Простых чисел бесконечно много?
Да — Евклид доказал это около 300 года до н. э. Допустим, существует наибольшее простое число; перемножим все известные простые числа и прибавим 1 — результат не делится ни на одно из них, значит, у него есть новый простой делитель. Простых чисел до миллиона — 78 498, а до триллиона примерно \(\pi(10^{12}) \approx 37.6\) миллиарда. Разрывы между простыми числами в среднем растут, но рекордные простые продолжают находить — в последних открытиях их длина превышает 24 миллиона цифр.