Составное число – это целое положительное число , которое можно получить путем умножения двух меньших положительных целых чисел. Эквивалентно, это положительное целое число, имеющее хотя бы один делитель , отличный от 1 и самого себя. [1] [2] Каждое положительное целое число является составным, простым или имеет единицу 1, поэтому составными числами являются именно те числа, которые не являются простыми и не являются единицей. [3] [4]
Например, целое число 14 является составным числом, поскольку оно является произведением двух меньших целых чисел 2 × 7. Аналогично, целые числа 2 и 3 не являются составными числами, поскольку каждое из них можно разделить только на единицу и на себя.
Составные числа до 150:
Каждое составное число можно записать как произведение двух или более (не обязательно различных) простых чисел. [2] Например, составное число 299 можно записать как 13 × 23, а составное число 360 можно записать как 2 3 × 3 2 × 5; более того, это представление уникально с точностью до порядка множителей. Этот факт называется основной теоремой арифметики . [5] [6] [7] [8]
Существует несколько известных тестов на простоту , которые могут определить, является ли число простым или составным, без необходимости выявления факторизации составного входного сигнала.
Один из способов классификации составных чисел — подсчет количества простых множителей. Составное число с двумя простыми делителями является полупростым или 2-почти простым (сомножители не обязательно должны быть различными, следовательно, включаются квадраты простых чисел). Составное число с тремя различными простыми делителями является сфеническим числом . В некоторых приложениях необходимо различать составные числа с нечетным числом различных простых множителей и числа с четным числом различных простых множителей. Для последнего
(где µ — функция Мёбиуса , а x — половина суммы простых множителей), а для первого
Однако для простых чисел функция также возвращает −1 и . Для числа n с одним или несколькими повторяющимися простыми делителями:
Если все простые множители числа повторяются, то оно называется мощным числом (все совершенные степени являются мощными числами). Если ни один из его простых множителей не повторяется, он называется безквадратным . (Все простые числа и 1 не содержат квадратов.)
Например, 72 = 2 3 × 3 2 , все простые множители повторяются, поэтому 72 — мощное число. 42 = 2 × 3 × 7, ни один из простых множителей не повторяется, поэтому число 42 не содержит квадратов.
Другой способ классификации составных чисел — подсчет количества делителей. Все составные числа имеют не менее трёх делителей. В случае квадратов простых чисел эти делители равны . Число n , у которого делителей больше, чем любое число x < n , является составным числом (хотя первые два таких числа — 1 и 2).
Составные числа также называют «прямоугольными числами», но это название также может относиться к проническим числам — числам, которые являются произведением двух последовательных целых чисел.
Еще один способ классификации составных чисел — определить, находятся ли все простые множители ниже или выше некоторого фиксированного (простого) числа. Такие числа называются гладкими числами и грубыми числами соответственно.