Разложение на простые множители и свойства натуральных чисел

Введение

Таблицы содержат разложение на простые множители натуральных чисел от 1 до 1000. Если n — простое число, то его разложение на простые множители состоит только из самого n, выделенного жирным шрифтом ниже. Число 1 называется единицей. Оно не имеет простых множителей и не является ни простым, ни составным.

Свойства

Многие свойства натурального числа n можно увидеть или напрямую вычислить из его разложения на простые множители.
Множитель простого множителя p числа n — это наибольший показатель m, при котором pm делит n. В таблицах показаны множители для каждого простого множителя. Если показатель не указан, то множитель равен 1 (поскольку p = p¹). Множитель простого числа, не делящего n, может быть назван 0 или считаться неопределенным. Ω(n), функция омега-функция, — это количество простых множителей n, подсчитанных с учетом их множителей (то есть это сумма всех множителей простых множителей). Для простого числа Ω(n) = 1. Первые: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37. Существует много специальных типов простых чисел. Составное число имеет Ω(n) > 1. Первые: 4, 6, 8, 9, 10, 12, 14, 15, 16, 18, 20, 21. Все числа больше 1 являются либо простыми, либо составными. 1 не является ни тем, ни другим. Полупростое число имеет Ω(n) = 2 (следовательно, оно составное). Первые: 4, 6, 9, 10, 14, 15, 21, 22, 25, 26, 33, 34. k-почти простое число (для натурального числа k) имеет Ω(n) = k (следовательно, оно составное, если k > 1). Четное число имеет простой множитель 2. Первые: 2, 4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24. Нечетное число не имеет простого множителя 2. Первые: 1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23. Все целые числа либо четные, либо нечетные. Квадрат имеет четный множитель для всех простых множителей (он имеет вид a² для некоторого a). Первые: 1, 4, 9, 16, 25, 36, 49, 64, 81, 100, 121, 144. Куб имеет все множители, кратные 3 (он имеет вид a³ для некоторого a). Первые: 1, 8, 27, 64, 125, 216, 343, 512, 729, 1000, 1331, 1728. Совершенная степень имеет общий делитель m > 1 для всех множителей (он имеет вид aᵐ для некоторых a > 1 и m > 1). Первые: 4, 8, 9, 16, 25, 27, 32, 36, 49, 64, 81, 100. 1 иногда включается. Мощное число (также называемое квадратным) имеет множитель больше 1 для всех простых множителей. Первые: 1, 4, 8, 9, 16, 25, 27, 32, 36, 49, 64, 72. Первая степень имеет только один простой множитель. Первые: 2, 3, 4, 5, 7, 8, 9, 11, 13, 16, 17, 19. 1 иногда включается. Число Ахиллеса — это мощное число, но не совершенная степень. Первые: 72, 108, 200, 288, 392, 432, 500, 648, 675, 800, 864, 968. Квадратично свободное целое число не имеет простых множителей с множителем больше 1. Первые: 1, 2, 3, 5, 6, 7, 10, 11, 13, 14, 15, 17. Число, в котором некоторые, но не все простые множители имеют множитель больше 1, не является ни квадратично свободным, ни квадратным. Функция Лиувилля λ(n) равна 1, если Ω(n) четно, и −1, если Ω(n) нечетно. Функция Мёбиуса μ(n) равна 0, если n не является квадратично свободным. В противном случае μ(n) равна 1, если Ω(n) четно, и −1, если Ω(n) нечетно. Сфеническое число имеет Ω(n) = 3 и является квадратично свободным (то есть является произведением 3 различных простых чисел). Первые: 30, 42, 66, 70, 78, 102, 105, 110, 114, 130, 138, 154. a₀(n) — это сумма простых чисел, делящих n, подсчитанная с учетом их множителей. Это аддитивная функция. Пара Рут-Аарона — это два последовательных числа (x, x+1) с a₀(x) = a₀(x+1). Первые (по значению x): 5, 8, 15, 77, 125, 714, 948, 1330, 1520, 1862, 2491, 3248. Другое определение — это одно и то же простое число, подсчитанное только один раз; если это так, то первые (по значению x): 5, 24, 49, 77, 104, 153, 369, 492, 714, 1682, 2107, 2299. Примириал x# — это произведение всех простых чисел от 2 до x. Первые: 2, 6, 30, 210, 2310, 30030, 510510, 9699690, 223092870, 6469693230, 200560490130, 7420738134810. 1# = 1 иногда включается. Факториал x! — это произведение всех чисел от 1 до x. Первые: 1, 2, 6, 24, 120, 720, 5040, 40320, 362880, 3628800, 39916800, 479001600. 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. k-степенно-гладкое число имеет все pm ≤ k, где p — простой множитель с множителем m. Экономное число имеет больше цифр, чем количество цифр в его разложении на простые множители (когда записано как в таблицах ниже с множителями больше 1 в качестве показателей). Первые в десятичной системе: 125, 128, 243, 256, 343, 512, 625, 729, 1024, 1029, 1215, 1250. Равноцифровое число имеет такое же количество цифр, как и его разложение на простые множители. Первые в десятичной системе: 1, 2, 3, 5, 7, 10, 11, 13, 14, 15, 16, 17. Экстравагантное число имеет меньше цифр, чем его разложение на простые множители. Первые в десятичной системе: 4, 6, 8, 9, 12, 18, 20, 22, 24, 26, 28, 30. Экономичное число определяется как экономное число, но также как число, которое является экономным или равноцифровым. НОД(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. Нахождение простых множителей часто сложнее, чем вычисление НОД и НОК с использованием других алгоритмов, которые не требуют известных простых множителей. m является делителем n (также называется m делит n или n делится на m), если все простые множители m имеют хотя бы такой же множитель в n. Делители n — это все произведения некоторых или всех простых множителей n (включая пустое произведение 1 без простых множителей). Количество делителей можно вычислить, увеличив все множители на 1, а затем перемножив их. Делители и свойства, связанные с делителями, показаны в таблице делителей.

Many properties of a natural number n can be seen or directly computed from the prime factorization of n.
The multiplicity of a prime factor p of n is the largest exponent m for which pm divides n. The tables show the multiplicity for each prime factor. If no exponent is written then the multiplicity is 1 (since p = p1). The multiplicity of a prime which does not divide n may be called 0 or may be considered undefined. Ω(n), the prime omega function, is the number of prime factors of n counted with multiplicity (so it is the sum of all prime factor multiplicities). A prime number has Ω(n) = 1. The first: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37 There are many special types of prime numbers. A composite number has Ω(n) > 1. The first: 4, 6, 8, 9, 10, 12, 14, 15, 16, 18, 20, 21 All numbers above 1 are either prime or composite. 1 is neither. A semiprime has Ω(n) = 2 (so it is composite). The first: 4, 6, 9, 10, 14, 15, 21, 22, 25, 26, 33, 34 A k almost prime (for a natural number k) has Ω(n) = k (so it is composite if k > 1). An even number has the prime factor 2. The first: 2, 4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24 An odd number does not have the prime factor 2. The first: 1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23 All integers are either even or odd. A square has even multiplicity for all prime factors (it is of the form a2 for some a). The first: 1, 4, 9, 16, 25, 36, 49, 64, 81, 100, 121, 144 A cube has all multiplicities divisible by 3 (it is of the form a3 for some a). The first: 1, 8, 27, 64, 125, 216, 343, 512, 729, 1000, 1331, 1728 A perfect power has a common divisor m > 1 for all multiplicities (it is of the form am for some a > 1 and m > 1). The first: 4, 8, 9, 16, 25, 27, 32, 36, 49, 64, 81, 100 1 is sometimes included. A powerful number (also called squareful) has multiplicity above 1 for all prime factors. The first: 1, 4, 8, 9, 16, 25, 27, 32, 36, 49, 64, 72 A prime power has only one prime factor. The first: 2, 3, 4, 5, 7, 8, 9, 11, 13, 16, 17, 19 1 is sometimes included. An Achilles number is powerful but not a perfect power. The first: 72, 108, 200, 288, 392, 432, 500, 648, 675, 800, 864, 968 A square free integer has no prime factor with multiplicity above 1. The first: 1, 2, 3, 5, 6, 7, 10, 11, 13, 14, 15, 17 A number where some but not all prime factors have multiplicity above 1 is neither square free nor squareful. The Liouville function λ(n) is 1 if Ω(n) is even, and is 1 if Ω(n) is odd. The Möbius function μ(n) is 0 if n is not square free. Otherwise μ(n) is 1 if Ω(n) is even, and is −1 if Ω(n) is odd. A sphenic number has Ω(n) = 3 and is square free (so it is the product of 3 distinct primes). The first: 30, 42, 66, 70, 78, 102, 105, 110, 114, 130, 138, 154 a0(n) is the sum of primes dividing n, counted with multiplicity. It is an additive function. A Ruth Aaron pair is two consecutive numbers (x, x+1) with a0(x) = a0(x+1). The first (by x value): 5, 8, 15, 77, 125, 714, 948, 1330, 1520, 1862, 2491, 3248 Another definition is the same prime only counted once; if so, the first (by x value): 5, 24, 49, 77, 104, 153, 369, 492, 714, 1682, 2107, 2299 A primorial x# is the product of all primes from 2 to x. The first: 2, 6, 30, 210, 2310, 30030, 510510, 9699690, 223092870, 6469693230, 200560490130, 7420738134810 1# = 1 is sometimes included. A factorial x! is the product of all numbers from 1 to x. The first: 1, 2, 6, 24, 120, 720, 5040, 40320, 362880, 3628800, 39916800, 479001600 0! = 1 is sometimes included. A k smooth number (for a natural number k) has its prime factors ≤ k (so it is also j smooth for any j > k). m is smoother than n if the largest prime factor of m is below the largest of n.
A regular number has no prime factor above 5 (so it is 5 smooth). The first: 1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15, 16 A k powersmooth number has all pm ≤ k where p is a prime factor with multiplicity m.
A frugal number has more digits than the number of digits in its prime factorization (when written like the tables below with multiplicities above 1 as exponents). The first in decimal: 125, 128, 243, 256, 343, 512, 625, 729, 1024, 1029, 1215, 1250 An equidigital number has the same number of digits as its prime factorization. The first in decimal: 1, 2, 3, 5, 7, 10, 11, 13, 14, 15, 16, 17 An extravagant number has fewer digits than its prime factorization. The first in decimal: 4, 6, 8, 9, 12, 18, 20, 22, 24, 26, 28, 30 An economical number has been defined as a frugal number, but also as a number that is either frugal or equidigital. gcd(m, n) (greatest common divisor of m and n) is the product of all prime factors which are both in m and n (with the smallest multiplicity for m and n). m and n are coprime (also called relatively prime) if gcd(m, n) = 1 (meaning they have no common prime factor). lcm(m, n) (least common multiple of m and n) is the product of all prime factors of m or n (with the largest multiplicity for m or n). gcd(m, n) × lcm(m, n) = m × n. Finding the prime factors is often harder than computing gcd and lcm using other algorithms which do not require known prime factorization. m is a divisor of n (also called m divides n, or n is divisible by m) if all prime factors of m have at least the same multiplicity in n.
The divisors of n are all products of some or all prime factors of n (including the empty product 1 of no prime factors). The number of divisors can be computed by increasing all multiplicities by 1 and then multiplying them. Divisors and properties related to divisors are shown in table of divisors.