Калькулятор простых и составных чисел

Введите расчет

Enter a whole number (n > 1)

Результатов

The number 97 is

Prime

divisible only by 1 and itself

Число	97

Что делает этот калькулятор

Этот инструмент определяет, является ли целое число простым или составным. У простого числа, большего 1, ровно два делителя: единица и само число. У составного числа есть хотя бы один дополнительный делитель. Числа 0 и 1 не относятся ни к простым, ни к составным, поэтому вводить нужно число от 2 и выше.

Как пользоваться

Введите в поле любое целое число и нажмите кнопку. Калькулятор покажет, к какому типу относится число, а если оно составное — выведет ещё и наименьший простой делитель и пример разложения на множители (наименьший делитель \(\times\) соответствующий ему сомножитель).

Как это работает: формула

Проверка строится на переборе делителей (пробном делении). Чтобы понять, составное ли число n, достаточно перебрать делители d от 2 до квадратного корня из n. Если хотя бы одно такое d делит n без остатка, то n — составное. Если ни одно не подходит — число простое. Перебор только до \(\sqrt{n}\) работает потому, что если \(n = a \times b\), то хотя бы один из множителей не превышает \(\sqrt{n}\).

$$\text{Prime if } \text{n} > 1 \text{ and } \nexists\, d \in [2, \lfloor\sqrt{\text{n}}\rfloor] : \text{n} \bmod d = 0$$

$$\begin{gathered} \text{Classify}(\text{n}) = \begin{cases} \text{Prime} & \nexists\, d \in [2,\lfloor\sqrt{\text{n}}\rfloor],\; \text{n} \bmod d = 0 \\[0.4em] \text{Composite} & \exists\, d \in [2,\lfloor\sqrt{\text{n}}\rfloor],\; \text{n} \bmod d = 0 \\[0.4em] \text{Neither} & \text{n} < 2 \end{cases} \end{gathered}$$

Реклама

Число составное, если у него есть делитель между 1 и квадратным корнем из него; иначе оно простое.

Разбор на примере

Возьмём \(n = 91\). Квадратный корень из 91 — примерно 9,54, поэтому проверяем 2, 3, 5, 7, 9. Получаем $$91 \div 7 = 13$$ без остатка, значит, 91 — составное число, его наименьший делитель равен 7, а разложение выглядит как \(7 \times 13\). Для сравнения: у числа 97 нет ни одного делителя вплоть до 9, поэтому оно простое.

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

Частые вопросы

Единица — простое число? Нет. По определению у простого числа должно быть ровно два различных положительных делителя, а у единицы он всего один.

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

Почему останавливаемся на квадратном корне? Любому делителю, большему \(\sqrt{n}\), соответствует парный делитель меньше \(\sqrt{n}\), который уже учтён при переборе. Поэтому проверять числа больше \(\sqrt{n}\) не имеет смысла.