Таблица простых множителей
Таблица содержит факторизацию натуральных чисел от 1 до 1000.
Если n — простое число (выделено жирным шрифтом ниже), то разложение состоит только из самого n.
Число 1 не имеет простых делителей и не является ни простым, ни составным числом.
Смотрите также: Таблица делителей (простые и составные делители чисел от 1 до 1000).
Свойства
Многие свойства натурального числа n можно увидеть или непосредственно вычислить из факторизации n.
- Степень m, в которой простое число p входит в факторизацию числа n — это наибольшее число, для которого n делится на pm. Для простых чисел, не входящих в факторизацию, полагают эту степень равной 0.
- Омега-функция (Ω(n)) — это сумма всех степеней, в которых простые числа входят в разложение n. Например, для 24 = 23 × 31, Ω(24) = 3 + 1 = 4.
- Для простых чисел Ω(n) = 1. Первые: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37 последовательность A000040 в OEIS. Существует много различных типов простых чисел. В диапазоне до 1000 встречаются, например, простые-близнецы ((3, 5), (5, 7), (11, 13), (17, 19), (29, 31), (41, 43), (59, 61), (71, 73), (101, 103), (881, 883))[1], простые числа Софи Жермен (2, 3, 5, 11, 23, 29, 41, 53, 83, 89, 113, 131, 173, 179, 191, 233, 239, 251, 281, 293, 359, 419, 431, 443, 491, 509, 593, 641, 653, 659, 683, 719, 743, 761, 809, 911, 953), простые-палиндромы (2, 3, 5, 7, 11, 101, 131, 151, 181, 191, 313, 353, 373, 383, 727, 757, 787, 797, 919, 929)[2], простые числа Мерсенна (3, 7, 31, 127) и простые числа Ферма (3, 5, 17, 257)[3].
- Составные числа имеют Ω(n) > 1. Первые: 4, 6, 8, 9, 10, 12, 14, 15, 16, 18, 20, 21 последовательность A002808 в OEIS. Все числа больше единицы простые или составные.
- Полупростые числа имеют Ω(n) = 2 (то есть они составные). Первые: 4, 6, 9, 10, 14, 15, 21, 22, 25, 26, 33, 34 последовательность A001358 в OEIS.
- m — делитель n (также говорят, m делит n, или n кратно m), если все простые числа входят в факторизацию m в степени, не большей чем степень, в которой они входят в факторизацию n.
- Чётные числа имеют простой делитель 2. Первые: 2, 4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24 последовательность A005843 в OEIS.
- Нечётные числа, наоборот, не имеют простого делителя 2. Первые: 1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23 последовательность A005408 в OEIS. Все целые числа чётные или нечётные.
- В факторизацию квадрата все простые делители входят в чётной степени. Первые: 1, 4, 9, 16, 25, 36, 49, 64, 81, 100, 121, 144 последовательность A000290 в OEIS.
- В факторизацию куба все простые делители входят в степени, делящейся на 3. Первые: 1, 8, 27, 64, 125, 216, 343, 512, 729, 1000, 1331, 1728 последовательность A000578 в OEIS.
- В факторизацию полнократных чисел все простые делители входят в степени, большей единицы. Первые: 1, 4, 8, 9, 16, 25, 27, 32, 36, 49, 64, 72 последовательность A001694 в OEIS.
- Степени простых числа имеют только один простой делитель. Первые: 2, 3, 4, 5, 7, 8, 9, 11, 13, 16, 17, 19 последовательность A000961 в OEIS.
- В факторизации бесквадратных чисел нет простых чисел в степени, большей 1. Первые: 1, 2, 3, 5, 6, 7, 10, 11, 13, 14, 15, 17 последовательность A005117 в OEIS).
- Функция Мёбиуса μ(n) равна 0, если n — не бесквадратное число. Иначе, μ(n) = 1, если Ω(n) чётно, и μ(n) = −1, если Ω(n) нечётно.
- Сфенические числа бесквадратны и имеют Ω(n) = 3, то есть они являются произведениями трёх различных простых чисел. Первые: 30, 42, 66, 70, 78, 102, 105, 110, 114, 130, 138, 154 последовательность A007304 в OEIS.
- Праймориал x# — это произведение всех простых чисел от 2 до x. Первые: 2, 6, 30, 210, 2310, 30030, 510510, 9699690, 223092870, 6469693230, 200560490130, 7420738134810 последовательность A002110 в OEIS. 1# = 1.
- Факториал x! — это произведение всех целых чисел от 1 до x. Первые: 1, 2, 6, 24, 120, 720, 5040, 40320, 362880, 3628800, 39916800, 479001600 последовательность A000142 в OEIS. 0! = 1.
- k-гладкие числа (для натурального k) имеют наибольший простой делитель ≤ k, то есть это также j-гладкие числа для любого j > k).
- m более гладкое чем n, если наибольший простой делитель m меньше, чем наибольший простой делитель n.
- У регулярных чисел нет простых делителей больше 5 (5-гладкие числа). Первые: 1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15, 16 последовательность A051037 в OEIS.
- НОД(m, n) (наибольший общий делитель m и n) — это произведение всех простых чисел, которые входят в факторизацию как m, так и n (причём в степени, наименьшей из m и n).
- m и n взаимнопросты, если НОД(m, n) = 1, то есть у них нет общий простых делителей.
- НОК(m, n) (наименьшее общее кратное m и n) — это произведение всех простых делителей m или n (причём в степени, наибольшей из m и n).
- НОК(m, n) × НОД(m, n) = m × n. Нахождение простых делителей часто сложнее, чем вычислять НОК и НОД алгоритмами, не требующими знание факторизации этих чисел.
1 — 200
|
|
201—400
|
|
401—600
|
|
601—800
|
|
801—1000
|
|
Алгоритмы
Для автоматизированного создания таблиц факторизации чисел до 1000 используются алгоритмы, которые значительно быстрее ручного разложения. Основными методами для такого диапазона являются пробное деление и алгоритмы на основе решета[4][5].
Метод пробного деления (перебор делителей) заключается в последовательном делении числа n на простые числа, начиная с 2, до тех пор, пока делитель не превысит квадратный корень из n. Если при делении остаток равен нулю, то найденный делитель является простым множителем. Процесс повторяется для частного от деления, пока в результате не останется 1. Для чисел до 1000 этот метод работает быстро, так как максимальный простой делитель, который необходимо проверить, не превышает 31[4].
Алгоритмы на основе решета (модификации решета Эратосфена) более эффективны для создания целой таблицы разложений. Вместо факторизации каждого числа по отдельности предварительно вычисляется массив наименьших простых делителей для всего диапазона от 2 до 1000. Для каждого простого числа p «просеиваются» все кратные ему числа, и если у них ещё не отмечен наименьший простой делитель, им присваивается p. С помощью такого массива любое число n раскладывается на множители путём последовательного деления на свой наименьший простой делитель до достижения единицы[5].
Более сложные алгоритмы, такие как ρ-алгоритм Полларда, метод эллиптических кривых или квадратичное решето, предназначены для факторизации очень больших чисел и являются избыточными для диапазона до 1000[6].
Визуализация
Помимо табличного представления, существуют графические способы визуализации разложения натуральных чисел на простые множители. Одним из таких методов являются рекурсивные диаграммы факторизации. В них каждый простой множитель числа определяет симметричное расположение составных частей (например, точек). Для простого множителя p группа из p элементов располагается симметрично, и этот процесс рекурсивно применяется ко всем простым делителям числа, образуя уникальную фракталоподобную структуру[7][8]. Для анализа распределения простых чисел также используется спираль Улама, в которой натуральные числа закручены в спираль, а простые числа часто выстраиваются вдоль диагональных линий, что позволяет наглядно визуализировать их распределение[9].
Примечания
Литература
- Абрамовиц М., Стиган И. Справочник по специальным функциям. М.: Наука, 1979. С. 646. (Табл.24.7. Разложения на множители)