Что такое составные числа и зачем они нужны

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

В статье разберем, чем простые числа отличаются от составных, какие свойства есть у составных чисел и как быстро определить, к какому типу относится число. Научимся раскладывать составные числа на простые множители и посмотрим, где это используется на практике. А также разберём, как проверять числа на составность и выполнять разложение на множители с помощью Python.

Простые и составные числа

Натуральные числа можно разделить на две основные категории: простые и составные.

Простое число — это целое число, которое больше единицы и делится без остатка исключительно на единицу и на само себя. Примерами таких чисел являются 2, 3, 5, 7, 11, 13, 17 и так далее.

Составное число — это натуральное число, превышающее единицу, которое имеет по крайней мере один делитель, отличный от единицы и самого числа. Например, число 4 является составным, поскольку помимо 1 и 4, оно делится на 2. Аналогично, 8 делится на 1, 2, 4 и 8, что также делает его составным.

Важно отметить, что число 2 — единственное четное простое число. Любое другое четное число делится на 2, имея таким образом как минимум три делителя (1, 2 и само число), что автоматически относит его к составным.

Основная теорема арифметики

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

К примеру, число 18 можно представить как \(2\cdot3\cdot3\), или, что то же самое в степенной записи, \(2=3^2\). Никакие иные комбинации простых множителей не дадут в результате 18. Именно эта уникальность разложения на простые множители отличает составные числа от простых, которые не поддаются дальнейшему разложению.

Например, число 17 является простым, поэтому его разложение состоит только из самого этого числа.

Нуль и единица

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

Единица исключена из простых чисел, чтобы не нарушать основную теорему арифметики. В противном случае, любое составное число имело бы бесконечное множество вариантов разложения на простые множители (например, \(18=2\cdot3^2\), \(18=1\cdot2\cdot3^2\), \(18=1\cdot1\cdot2\cdot3^2 \) и т.д.), что разрушило бы стройность теории чисел.

Ноль не рассматривается в контексте простых и составных чисел по нескольким причинам: он делится на любое число, кроме себя, что дает бесконечное количество делителей; деление на ноль не определено; и, наконец, в классической теории чисел ноль не считается натуральным числом.

Разложение на простые множители

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

Основной принцип такого разложения заключается в последовательном делении исходного и последующих в частном чисел на наименьшие простые числа (2, 3, 5 и т.д.), пока в частном не получится простое число. В конце нужно перемножить все делители и простое число в последнем частном. Далее рассмотрим несколько практических примеров.

Разложим на простые множители число 12. Число 12 четное, а значит, делится на 2:

12 : 2=6

Число 6 тоже четное, поэтому также делим его на 2:

6 : 2=3

Число 3 является простым, а значит, процесс разложения завершен. Итак, мы два раза делили на 2 и в самом конце получили число 3. Перемножаем делители и число 3:

Теперь так же попробуем разложить число 30. Так как это число тоже четное, то делим его пополам:

30 : 2=15

А вот 15 уже число нечетное и наименьшее простое число, на которое оно делится — 3. Делим на 3:

15 : 3=5

Получили простое число 5. Разложение завершено. Перемножаем делители и число 5:

Возьмем число побольше. Разложим на простые множители число 945. Оно нечетное, поэтому проверяем его делимость на 3. Сумма его цифр делится на 3 (9+4+5=18), поэтому и само число делится на 3:

945 : 3=315

Число 315 тоже нечетное и делится на 3:

315 : 3=105

Этот результат тоже делим на 3:

105 : 3=35

Число 35 не делится на 2 и 3, зато прекрасно делится на 5:

35 : 5=7

Все! Получили простое число 7. Составляем произведение из делителей и последнего частного:

Возьмем число еще больше, а именно 2310. Оно четное, а значит, прекрасно делится пополам:

2310 : 2=1155

Далее делим результат на 3:

1155 : 3=385

Здесь придется делить на 5:

385 : 5=77

Число 77 не делится на 2, 3 и 5, но делится на 7:

77 : 7=11

Посмотрим, что у нас получилось. Выписываем все делители и последнее частное в виде произведения:

Как видим, число 2310 раскладывается на произведение первых пяти простых чисел. Все множители находятся в первой степени. А еще есть число 75600. Его разложение имеет такой вид:

Множители здесь — это первые 4 простых числа, а их степени идут по убыванию. Или есть вот такой монстр с возрастающими показателями степеней:

При желании можете сами проверить результаты этих разложений.

Как проверить составность числа

Чтобы проверить является ли число составным, необязательно проверять его делители от 2 до самого этого числа. Достаточно всего лишь проверить делители от 2 до квадратного корня из этого числа. Почему так?

Все довольно просто. Пусть \(n={a}\cdot{b}\), где \({a}\le{b}\). Если умножить обе части неравенства на a, то получим уже такое неравенство:

Или, что то же самое:

Откуда получим:

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

Простой пример. Возьмем число 36. Корень из него равен 6. Из промежутка от 2 до 6 число 36 делится на 2, 3, 4 и 6. Значит, число 36 составное. Вообще, достаточно найти всего лишь один делитель из этого промежутка, чтобы сказать, что число составное.

Или возьмем число 17. Корень из него примерно равен 4,12. Округлим до 4. От 2 до 4 включительно делителей у 17 нет. Значит это простое число.

Признаки делимости

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

• 2, если его последняя цифра четная.

• 5, если последняя цифра числа — 0 или 5.

• 10, если число оканчивается на 0.

• 4, если число, образованное двумя его последними цифрами, делится на 4, или если эти две последние цифры — нули.

• 25, если число завершается на 00, 25, 50 или 75.

• 8, если число, образованное тремя его последними цифрами, делится на 8, или если эти три последние цифры — нули.

• 3, если сумма всех цифр числа делится на 3.

• 9, если сумма его цифр делится на 9.

• 6, если оно одновременно делится на 2 (является четным) и на 3 (сумма его цифр кратна 3).

• 12, если оно делится как на 3, так и на 4.

• 15, если оно делится и на 3, и на 5.

• 11, если разница между суммой цифр, стоящих на нечетных позициях, и суммой цифр на четных позициях делится на 11 или равна нулю.

Владение этими признаками делимости значительно облегчает процесс разложения чисел на простые множители.

Свойства составных чисел

Перечислим некоторые свойства составных чисел:

• У любого составного числа более двух делителей: 1, само это число и как минимум еще одно.

• Всякое составное число можно представить в виде произведения степеней простых чисел, причем такое представление единственное.

• Составных чисел бесконечное множество.

• Все четные числа, начиная с 4 — составные.

• По мере возрастания чисел составные числа встречаются чаще, а простые — реже.

• Если число оканчивается на цифру 5 (кроме самого числа 5), то оно составное.

• Если сумма цифр числа делится на 3 или на 9 и число больше этих делителей, то оно является составным.

• Наименьший простой делитель составного числа не больше квадратного корня из этого числа.

Какие бывают составные числа

Составные числа бывают самые разные. Вот только некоторые их разновидности:

• Полупростые числа — это составные числа, которые раскладываются на два простых числа. Таким числом, например, является 14, так как \(14=2\cdot7\).

• Сфенические числа. Эти числа равны произведению трех различных простых чисел. Например: \(66=2\cdot3\cdot11\).

• Степени простых чисел. Разложение таких чисел состоит из повторяющихся множителей. Примеры: \(49=7^2\), \(8=2^3\), \(81=3^4\).

• Полнократные числа. У таких чисел в разложении нет одиночных множителей. Каждый множитель входит в разложение в степени не меньше 2. Примеры: \(36=2^2\cdot3^2\), \(72=2^3\cdot3^2\).

• Бесквадратные числа — это числа, в разложении которых нет повторяющихся множителей. Уже упомянутые выше сфенические числа — это частный случай бесквадратных чисел. Пример: \(70=2\cdot5\cdot7\).

• Избыточные числа — это такие числа, у которых сумма всех делителей, без самого числа, больше этого самого числа. Например, у числа 12 сумма делителей равна 16 (1+2+3+4+6=16). А раз 16 > 12, то число 12 избыточное.

• Сверхсоставные (высокосоставные) числа — это натуральные числа, которые имеют больше делителей, чем любое меньшее натуральное число. Примеры: 12, 24, 36.

• Прямоугольные числа. Разложение этих чисел имеет вид: n(n+1). То есть прямоугольное число равно произведению двух последовательных натуральных чисел. Такие числа всегда составные. Пример: \(6=2\cdot3\).

Применение составных чисел

Составные числа нашли свое применение в самых разных областях человеческой деятельности. Рассмотрим некоторые из них.

• Криптография. В некоторых алгоритмах шифрования открытый ключ содержит большое полупростое число. Безопасность основывается на том, что такое число трудно разложить на множители. Его разложение, в свою очередь, находится в закрытом ключе.

• Измерение времени. Все знают, что в часе 60 минут, в минуте 60 секунд, а в сутках 24 часа. Все эти числа — составные и у них много делителей. Из-за этого время очень удобно делить на равные части.

• Музыка. При создании сложных ритмов в тактовых размерах (4/4, 6/8, 12/8) используют составные числа, чтобы можно было гибко дробить доли.

• Веб-дизайн и полиграфия. Размеры сеток и колонок часто подбирают так, чтобы общее число отдельных элементов было составным. Такой подход упрощает деление на составляющие без дробных значений.

• Головоломки. Игровые поля, количество фишек и карт часто делают составным, чтобы у игроков было больше вариантов разбиений, комбинаций и стратегий.

• Экономика. Традиционные меры и денежные единицы (дюжина, либра, мина, золотник, рупия, фунт) исторически связаны с удобством деления на части при продаже и учете товаров.

Составные числа в Python

В программировании довольно часто приходится иметь дело с составными числами. Давайте посмотрим, как можно определить составность числа и разложить его на простые множители, используя для этого популярный язык программирования Python.

Ниже приводится код простой функции is_composite_fast, которая проверяет является ли данное число составным:

import math

def is_composite_fast(n):
    if n <= 3:
        return False
    # Ищем делители от 2 до корня из n
    for i in range(2, math.isqrt(n) + 1):
        if n % i == 0:
            return True
    return False

Функция вернет False в случае, если проверяемое число меньше или равно 3. Это и понятно: числа 2 и 3 — простые, а 0 и 1 не являются ни простыми, ни составными. Далее запускается цикл for. Этот цикл последовательно проходится по числам из промежутка от 2 до квадратного корня из числа. Если попадается число из промежутка, на которое делится проверяемое число без остатка, то функция сразу же возвращает True. В противном случае будет возвращено False. Проверим эту функцию в работе:

print(is_composite_fast((6))
print(is_composite_fast((12))
print(is_composite_fast((128))
print(is_composite_fast((17))
print(is_composite_fast((1))
print(is_composite_fast((0))

Результат:

True
True
True
False
False
False

Что касается разложения на простые множители, то рассмотрим 2 варианта. Первый вариант выводит результат в виде простого списка множителей. Код:

def prime_factorization(n):
    factors = []
    d = 2
    # Поиск простых множителей
    while d * d <= n:
        if n % d == 0:
            factors.append(d)
            n //= d
        else:
            d += 1
    if n > 1:
        factors.append(n)
    return factors

Здесь используется список factors, в который посредством цикла while добавляются элементы (множители). Посмотрим, как работает эта функция:

print(prime_factorization(12))
print(prime_factorization(30))
print(prime_factorization(56))
print(prime_factorization(90))
print(prime_factorization(100))
print(prime_factorization(231))  

Результат:

[2, 2, 3]
[2, 3, 5]
[2, 2, 2, 7]
[2, 3, 3, 5]
[2, 2, 5, 5]
[3, 7, 11]

Второй вариант выводит результат разложения уже в более лаконичном виде с показателями степеней. Код функции:

from collections import Counter

def prime_factorization(n):
    original_n = n
    factors = []
    d = 2

    # Поиск простых множителей
    while d * d <= n:
        if n % d == 0:
            factors.append(d)
            n //= d
        else:
            d += 1
    if n > 1:
        factors.append(n)

    # Подсчет количества каждого множителя
    counts = Counter(factors)

    # Форматирование элементов (например, '2^2' или '3')
    parts = []
    for factor in sorted(counts.keys()):
        power = counts[factor]
        if power > 1:
            parts.append(f"{factor}^{power}")
        else:
            parts.append(f"{factor}")

    # Объединение в итоговую строку
    return f"{original_n} = {' * '.join(parts)}"

В первой части функции, как и в первом варианте, идет формирование списка в цикле while. Но дальше, чтобы вывести результат в необходимом виде пришлось использовать специальный счетчик Counter из модуля collections. На вход счетчика подаем готовый список factors и получаем объект counts. В нем хранится частотный словарь, созданный из списка factors. В этом словаре ключами являются множители, а значения ключей — это количество множителей. Далее цикл for проходит по частотному словарю, формируя новый список parts. В конце функция возвращает итоговую строку. Проверим работу функции на тех же числах:

print(prime_factorization(12))
print(prime_factorization(30))
print(prime_factorization(56))
print(prime_factorization(90))
print(prime_factorization(100))
print(prime_factorization(231))

Получим уже такой результат:

12 = 2^2 * 3
30 = 2 * 3 * 5
56 = 2^3 * 7
90 = 2 * 3^2 * 5
100 = 2^2 * 5^2
231 = 3 * 7 * 11

Все работает, как надо!