Разложение на простые множители
Простые множители, проверка на простоту, делители и деление столбиком.
- Мгновенно
- Бесплатно
- Приватно (обработка локально)
- Без регистрации
Разложить число на простые множители и проверить, простое ли оно
Любое целое число от 2 и больше записывается как произведение простых чисел единственным образом (с точностью до порядка множителей): это основная теорема арифметики. 360 = 23 × 32 × 5, 1 001 = 7 × 11 × 13, а 97 разложить нельзя вовсе: оно простое. Калькулятор даёт разложение, сразу сообщает, простое число или составное, и показывает разложение столбиком так, как его записывают на уроке.
Разложение лежит в основе многих вычислений: сокращения дробей, поиска НОД и НОК, подсчёта делителей, упрощения квадратных корней. Оно нужно школьникам 6 класса и старшеклассникам, учителям при подготовке заданий, участникам олимпиад и тем, кто готовится к ОГЭ и ЕГЭ, а также всем, кому интересна криптография: стойкость RSA держится на том, что очень большие числа трудно разложить на множители.
-
Введите число
Наберите целое число в поле «Целое число для разложения» (не меньше 2, до 18 цифр). Пробелы и разделители разрядов игнорируются, поэтому 600 851 475 143 можно вводить как есть. Кнопки рядом с «Примеры:» подставляют готовые числа.
-
Прочитайте вердикт
Надпись вверху сообщает: «Простое число» или «Не простое: составное число»; ниже появляется разложение с показателями степени (360 = 2³ × 3² × 5) и развёрнутая запись. Кнопка «Копировать» помещает 2^3 × 3^2 × 5 в буфер обмена.
-
Изучите свойства
Карточки «Арифметические свойства» показывают τ(n), σ(n), φ(n), количество различных простых множителей ω(n) и с учётом кратности Ω(n), является ли n полным квадратом, сумму собственных делителей, а также предыдущее и следующее простое число (до 10¹²).
-
Проверьте вручную
Таблица «Разложение столбиком (последовательное деление)» повторяет каждый шаг (360 ÷ 2 = 180…) до частного 1, а «Все делители» выводит делители по возрастанию, выделяя простые.
Метод: основная теорема арифметики и формулы
Для целого n ≥ 2 разложение записывается как n = p1a1 × p2a2 × … × pkak. Его получают, деля на наименьший простой множитель, пока это возможно; делители достаточно проверять до √n, потому что у составного числа всегда есть простой множитель, не превосходящий его квадратного корня.
Для больших чисел инструмент выполняет три этапа: пробное деление на простые числа до 10 000, детерминированный тест Миллера-Рабина для распознавания простых и ро-алгоритм Полларда (вариант Брента) для разложения оставшихся составных множителей. Все вычисления ведутся в точных целых числах, без округлений.
- p1 < p2 < … < pk: различные простые множители в порядке возрастания; их количество обозначают ω(n).
- ai: показатель степени (кратность) pi; сумма a1 + … + ak равна Ω(n), числу простых множителей с учётом повторений.
- τ(n) = (a1 + 1)(a2 + 1)…(ak + 1): количество делителей, так как делитель выбирает для каждого pi показатель от 0 до ai.
- σ(n) = ∏ (piai+1 − 1) / (pi − 1): сумма всех делителей; s(n) = σ(n) − n показывает, совершенное число, избыточное или недостаточное.
- φ(n) = n × ∏ (1 − 1/pi): функция Эйлера, то есть количество чисел от 1 до n, взаимно простых с n.
- Полный квадрат: n является квадратом тогда и только тогда, когда все ai чётны; тогда √n = ∏ piai/2, например √1 024 = 25 = 32.
Примеры разложения на простые множители
| Число | Разложение | τ(n) | σ(n) | φ(n) |
|---|---|---|---|---|
| 360 | 23 × 32 × 5 | 24 | 1 170 | 96 |
| 97 | простое | 2 | 98 | 96 |
| 1 001 | 7 × 11 × 13 | 8 | 1 344 | 720 |
| 1 024 | 210 (полный квадрат, 322) | 11 | 2 047 | 512 |
| 600 851 475 143 | 71 × 839 × 1 471 × 6 857 | 16 | 610 544 148 480 | 591 194 251 200 |
| 999 999 999 999 999 989 | простое | 2 | n + 1 | n − 1 |
Те же значения, что показывает инструмент. Для простого числа n имеем σ(n) = n + 1 и φ(n) = n − 1; соседние простые числа для 97: 89 и 101.
Где применяется разложение на простые множители?
- Сокращение дробей: 84/360 = (22 × 3 × 7)/(23 × 32 × 5) = 7/30 после сокращения общих множителей 22 × 3 = 12.
- Общий знаменатель: НОК чисел 360 и 84 равен 2 520, это наименьший общий знаменатель для сложения 1/360 и 1/84.
- Упрощение корней: √360 = √(22 × 32 × 10) = 2 × 3 × √10 = 6√10: каждую пару одинаковых множителей выносим из-под корня.
- Подсчёт и перечень делителей: полезно в задачах на деление поровну (расставить 360 стульев в одинаковые ряды можно 24 способами, ряды × столбцы) и в домашних заданиях по делимости.
- Криптография и задачи: RSA опирается на трудность разложения; знаменитая задача 3 Project Euler просит найти наибольший простой делитель числа 600 851 475 143, это 6 857.
Частые ошибки
- Деление на составное число: деление 360 на 4 или на 6 даёт верное частное, но неполное разложение; делить нужно только на 2, 3, 5, 7, 11, 13…
- Считать 1 простым числом: у единицы один делитель, и она никогда не входит в разложение.
- Путать 23 и 2 × 3: 23 = 2 × 2 × 2 = 8, а 2 × 3 = 6; показатель степени равен числу повторений множителя.
- Принимать за простое число, которое «так выглядит»: 51 = 3 × 17, 91 = 7 × 13 и 1 001 = 7 × 11 × 13 составные; всегда проверяйте до квадратного корня.
Все вычисления выполняются локально в вашем браузере с точной целочисленной арифметикой (BigInt): ни одно число не отправляется и не сохраняется. Ограничения: не более 18 цифр; соседние простые числа показываются до 1012, список делителей до 1 000 делителей, а таблица деления до 40 простых множителей с учётом кратности.
Частые вопросы
Почему 1 не является простым числом?
У простого числа ровно два различных делителя, 1 и само число, а у единицы делитель только один. Главное же в том, что иначе разложение перестало бы быть единственным: 360 = 2³ × 3² × 5 = 1 × 2³ × 3² × 5 = 1² × 2³ × 3² × 5 и так далее. Поэтому 1 не относится ни к простым, ни к составным числам, и инструмент не принимает его, объясняя причину.
Как разложить число на простые множители вручную?
Делим на наименьшее простое число, на которое число делится нацело, и повторяем с частным, пока не получим 1: 360 ÷ 2 = 180, 180 ÷ 2 = 90, 90 ÷ 2 = 45, 45 ÷ 3 = 15, 15 ÷ 3 = 5, 5 ÷ 5 = 1. Выписав простые делители, получаем 360 = 2³ × 3² × 5. Проверять дальше квадратного корня не нужно: √97 ≈ 9,8, поэтому достаточно попробовать 2, 3, 5 и 7, чтобы доказать, что 97 простое.
Как найти количество делителей по разложению?
К каждому показателю прибавляем 1 и перемножаем: для 360 = 2³ × 3² × 5 получаем τ(360) = (3+1)(2+1)(1+1) = 24 делителя. Для 1 001 = 7 × 11 × 13 выходит 2 × 2 × 2 = 8. Сумма делителей считается по той же логике: σ(360) = 15 × 13 × 6 = 1 170.
Как найти НОД и НОК через простые множители?
Раскладываем оба числа: 360 = 2³ × 3² × 5 и 84 = 2² × 3 × 7. В НОД входят общие множители с наименьшим показателем (2² × 3 = 12), в НОК все множители с наибольшим показателем (2³ × 3² × 5 × 7 = 2 520). Проверка: 12 × 2 520 = 30 240 = 360 × 84.
Как проверить, простое ли большое число?
Пробное деление до квадратного корня быстро становится непосильным: для 18-значного числа пришлось бы перебрать все простые числа до 10⁹. Поэтому инструмент применяет тест Миллера-Рабина с первыми 12 простыми числами (от 2 до 37) в качестве оснований: доказано, что для чисел меньше 3 × 10²³ он никогда не ошибается. В пределах 18 цифр (меньше 10¹⁸) ответ «простое» означает уверенность, а не вероятность. Даже самый трудный случай, произведение двух 9-значных простых, например 999 999 929 × 999 999 937, раскладывается за доли секунды.
Зачем нужна функция Эйлера φ(n)?
φ(n) считает числа от 1 до n, не имеющие общих множителей с n: φ(360) = 360 × (1 − 1/2)(1 − 1/3)(1 − 1/5) = 96. Для простого p имеем φ(p) = p − 1, поэтому φ(97) тоже равно 96. Она применяется и в шифровании RSA: для n = p × q значение φ(n) = (p − 1)(q − 1) нужно для вычисления закрытого ключа.