Калькулятор простых множителей

360 = 2^3 * 3^2 * 5; Ω(360) = 3 + 2 + 1 = 6; d(360) = (3+1) * (2+1) * (1+1) = 24

n

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

p

Простой множитель — простое число, которое делит n нацело. Страница находит их перебором делителей по возрастанию, поэтому наименьшее простое всегда вынимается первым и напечатанное разложение всегда идёт от меньшего простого к большему. Для 360 это 2, 3 и 5, и никакое другое простое его не делит

e

Показатель степени при простом — сколько раз это простое входит в произведение. 360 — это 2 × 2 × 2 × 3 × 3 × 5, поэтому 2 входит три раза, а 3 дважды. Простое, которое входит один раз, печатается вообще без показателя: пятёрка в 360 записывается как обычная 5, а не как 5^1, — это обычное соглашение, и оно сохраняет короткие разложения читаемыми

2^3 * 3^2 * 5

Разложение 360 в напечатанном виде и значение по умолчанию. Крышка означает показатель степени, звёздочка — умножение, поэтому вся запись переживает копирование в текстовое поле или в строку поиска. Такое выражение для каждого целого больше 1 ровно одно, и именно поэтому его стоит печатать: 360 нельзя записать ещё и каким-нибудь другим произведением простых

Ω(360) = 3 + 2 + 1 = 6

Число простых множителей с учётом повторов: три двойки, две тройки и одна пятёрка дают шесть. Именно это число и удивляет, потому что 360 как будто собрано из трёх простых, а не из шести. Рецепт — сложить показатели, а не считать различные простые, и ответы расходятся всякий раз, когда хоть один показатель больше 1. Записывается это греческой заглавной омегой

d(360) = (3+1) * (2+1) * (1+1) = 24

Число положительных делителей, полученное из тех же показателей: к каждому прибавляем единицу и перемножаем. Список — 1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15, 18, 20, 24, 30, 36, 40, 45, 60, 72, 90, 120, 180 и 360, всего двадцать четыре. Это другой вопрос, чем предыдущий: он считает числа, которые делят 360, а не простые, из которых оно построено

Разложение нужно тогда, когда вопрос о мультипликативной структуре числа, а не о его величине. Сокращение дроби или упрощение корня — повседневный случай: квадратный корень из 72 упрощается до 6√2, потому что 72 = 2³ × 3², а показатель при каждом простом говорит, сколько его можно вынести из-под знака корня, — это то же самое разложение, которое читает страница корней. Поиск наибольшего общего делителя или наименьшего общего кратного двух чисел — тоже оно, выполненное по разу на число: общие простые в меньших степенях дают первое, а все простые в больших степенях — второе. Вопросы делимости решаются так же, ведь одно число делит другое ровно тогда, когда его простые и показатели имеются в другом. В теории чисел разложение решает, простое ли число, сколько у него делителей, является ли оно полным квадратом (все показатели чётные) и является ли оно полным кубом. Стоит знать и границы метода: перебор делителей быстр на миллионе и безнадёжен на стозначном числе, и именно на этом разрыве между лёгким и трудным держится криптография с открытым ключом. Когда вопрос в том, какие числа делят ваше, а не какие простые его строят, их перечисляет страница делителей; когда вопрос в том, простое ли оно вообще, на это прямо отвечает страница простых чисел.

1. Значение по умолчанию: 360

   1. 360 чётное, делим на 2: 360 / 2 = 180, затем 180 / 2 = 90, затем 90 / 2 = 45 — всего три раза
   2. 45 нечётное; следующее простое — 3, и 45 / 3 = 15, затем 15 / 3 = 5 — дважды
   3. 5 простое, значит разложение — 2 × 2 × 2 × 3 × 3 × 5, то есть 2^3 * 3^2 * 5
   4. Считаем простые множители с повторами: 3 + 2 + 1 = 6
   5. Считаем делители по показателям: (3 + 1) × (2 + 1) × (1 + 1) = 4 × 3 × 2 = 24

   Значение по умолчанию и тот случай, который объясняет, зачем вообще печатать два числа. Шесть и двадцать четыре стоят рядом, и читатель, ожидающий, что они совпадут, решит, что одно из них сломано. Это не так: шесть — это сколько простых кусочков в числе, если сохранять каждый повтор, а двадцать четыре — сколько чисел его делят. Разрыв между ними берётся из показателей: каждый повтор простого умножает число делителей, почти не прибавляя к числу кусочков. Проверьте любое из двух вручную — арифметика короткая; проверьте оба — и запомните, какое из них какое.

2. Малый случай, где виден разрыв: 12

   1. 12 / 2 = 6, а 6 / 2 = 3, значит 2 входит дважды
   2. 3 простое, значит разложение — 2^2 * 3
   3. Считаем простые множители с повторами: 2 + 1 = 3, это 2, 2 и 3
   4. Выписываем делители: 1, 2, 3, 4, 6, 12 — их шесть
   5. Проверяем по рецепту: (2 + 1) × (1 + 1) = 3 × 2 = 6, что совпадает со списком

   Самый ясный малый пример той путаницы, ради которой сделана эта страница: оба числа достаточно малы, чтобы проверить их вручную за секунды. Двенадцать состоит из трёх простых — 2, 2 и 3, — и шесть чисел его делят. Прочитать вывод как «3 делителя» или «6 простых множителей» одинаково правдоподобно, и оба раза неверно. Список делителей показывает и то, откуда берётся чётность шести: 1 в паре с 12, 2 с 6, 3 с 4. Двенадцать не является полным квадратом, поэтому ни один делитель не образует пару с самим собой, и оттого количество чётное.

3. Неудобный случай: 1

   1. 1 не делится ни на одно простое — деление на 2, 3, 5 или любое другое даёт дробь
   2. Значит, простых множителей нет, и число их равно 0
   3. Единственное положительное число, которое делит 1, — это само 1, поэтому число делителей равно 1
   4. Разложение печатается как единственная цифра 1, а не как пустое поле

   Случай, который приходится решать, а не выводить, и решение — печатать 1. Пустое разложение читалось бы как «не посчиталось», а это единственное, на что панель результата не имеет права быть похожей. Оба числа после этого получаются честно: простых нет вообще, а делитель один. Единица не является ни простым, ни составным — она нейтральный элемент умножения, число, которое ничего не меняет при умножении на него, — и страница не делает вид, что это не так. Она принимается, а не отклоняется, потому что диапазон ввода начинается с 1, а диапазон, исключающий собственное нижнее значение, объяснять было бы куда страннее.

Ввод должен быть целым числом от 1 до 1 000 000. Ноль отклоняется: любое простое делит ноль, поэтому произведение пришлось бы делать бесконечным. Отрицательные числа отклоняются по родственной причине — простые делят и их, но знак пришлось бы нести отдельно, а утверждение об однозначности разложения касается положительных чисел. Дроби отклоняются, а не округляются: округление молча ответило бы на вопрос о другом числе. Потолок в миллион взят из общего модуля теории чисел и связан со стоимостью, а не с правильностью: перебор делителей до квадратного корня быстр на миллионе и безнадёжен на числе из двадцати цифр. Это настоящее свойство метода, и ровно оно делает работоспособной криптографию с открытым ключом. Страница сообщает разложение и два числа, и больше ничего: она не выписывает сами делители, не считает наибольший общий делитель или наименьшее общее кратное для нескольких чисел и не упрощает корни или дроби. Показатель степени 1 не печатается никогда, поэтому простое, входящее один раз, показывается голым числом, а знаком умножения всюду служит звёздочка — значит, вывод представляет собой чистый ASCII без разделителей разрядов. И наконец, справочная таблица ниже показывает четыре фиксированных числа, а не следует за вашим вводом.

В чём разница между двумя числами на этой странице?

Первое считает простые множители с сохранением повторов, второе — делители. Для 12 ответы 3 и 6, и оба верны. Двенадцать — это 2 × 2 × 3, значит оно состоит из трёх простых кусочков; и 1, 2, 3, 4, 6 и 12 все делят его, значит делителей шесть. Путаница естественна, потому что на малых вводах эти числа стоят близко. Рецепт для первого — сложить показатели; рецепт для второго — прибавить к каждому показателю единицу и перемножить. Именно из-за умножения второй счётчик разбегается куда быстрее: каждый лишний повтор простого умножает число делителей, прибавляя к первому всего единицу.

Разложение на простые множители у числа только одно?

Да, и это теорема, а не соглашение. Каждое целое число больше 1 можно записать в виде произведения простых, и, если пренебречь порядком, сделать это можно ровно одним способом. Триста шестьдесят — это только 2³ × 3² × 5, и никакое другое произведение простых им не является. Результат называется основной теоремой арифметики, и без неё печатать разложение было бы забавным фактом, а не ответом. Она же объясняет, почему страница может печатать наименьшее простое первым и быть уверенной, что это каноническая форма: порядок выбран для читаемости, и от его фиксации ничего не теряется.

Что страница делает с 1?

Печатает 1 как разложение, с нулём простых множителей и одним делителем. Единица не является ни простым, ни составным: разложения на простые у неё нет в обычном смысле, и теорема выше сформулирована для чисел больше 1 именно поэтому. Но пустая панель результата читалась бы как «не посчиталось», поэтому страница печатает цифру и честно сообщает оба числа. Число делителей у 1 действительно равно 1, ведь единственное положительное число, делящее 1, — это само 1, а число простых множителей действительно равно 0. Единица принимается, а не отклоняется, потому что диапазон ввода начинается с 1: отклонять собственное нижнее значение пришлось бы объяснять дольше, чем на него отвечать.

Почему остановка на миллионе?

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

Когда нужно разложение, а не список делителей?

Когда вопрос о структуре, а не о принадлежности. Чтобы упростить квадратный корень из 72, нужно 72 = 2³ × 3²: показатели говорят, сколько каждого простого можно вынести из-под знака корня, и получается 6√2. Чтобы найти наибольший общий делитель двух чисел, нужны оба разложения: ответ — общие простые в меньших степенях. Проверить, является ли число полным квадратом, — это взгляд на показатели: все чётные значит да. Перечисление делителей — другой вопрос, и в зависимости от числа ответ может быть куда длиннее: у 720 720 их 240, а это много для печати и мало для чтения. Страница делителей на этом сайте перечисляет их, когда нужны именно они.

Почему показатель не печатается, когда простое входит один раз?

Потому что писать 5^1 для единственной пятёрки — шум. В математике принято печатать показатель только тогда, когда он больше единицы, поэтому 360 — это 2^3 * 3^2 * 5, где последний член голый. От выбрасывания ничего не теряется: отсутствие показателя однозначно означает, что показатель равен единице, а разложение, целиком состоящее из одиночных простых, — а именно таково любое число без квадратов, — читается как обычное произведение вообще без крышек. По тому же соглашению 97, которое простое, печатается просто как 97, а не как 97^1.

• Prime Factorization — writing a whole number as a product of primes, and the algorithms that find the primes — Wolfram MathWorld (United States)
• Fundamental Theorem of Arithmetic — the statement that every whole number above 1 has exactly one prime factorization, which is what makes printing it worth doing — Wolfram MathWorld (United States)
• Divisor Function — the count of positive divisors, the formula that builds it from the exponents, and how it behaves on powers of a single prime — Wolfram MathWorld (United States)