composite number

TheInfoList

A composite number is a
positive integer In mathematics Mathematics (from Ancient Greek, Greek: ) includes the study of such topics as quantity (number theory), mathematical structure, structure (algebra), space (geometry), and calculus, change (mathematical analysis, analysis). ...
that can be formed by multiplying two smaller positive integers. Equivalently, it is a positive integer that has at least one
divisor In mathematics Mathematics (from Ancient Greek, Greek: ) includes the study of such topics as quantity (number theory), mathematical structure, structure (algebra), space (geometry), and calculus, change (mathematical analysis, analysis). ...

other than 1 and itself. Every positive integer is composite,
prime A prime number (or a prime) is a natural number greater than 1 that is not a Product (mathematics), product of two smaller natural numbers. A natural number greater than 1 that is not prime is called a composite number. For example, 5 is prime ...
, or the
unit Unit may refer to: Arts and entertainment * UNIT Unit may refer to: Arts and entertainment * UNIT, a fictional military organization in the science fiction television series ''Doctor Who'' * Unit of action, a discrete piece of action (or beat) in ...
1, so the composite numbers are exactly the numbers that are not prime and not a unit. For example, the integer is a composite number because it is the product of the two smaller integers  × . Likewise, the integers 2 and 3 are not composite numbers because each of them can only be divided by one and itself. The composite numbers up to 150 are :4, 6, 8, 9, 10, 12, 14, 15, 16, 18, 20, 21, 22, 24, 25, 26, 27, 28, 30, 32, 33, 34, 35, 36, 38, 39, 40, 42, 44, 45, 46, 48, 49, 50, 51, 52, 54, 55, 56, 57, 58, 60, 62, 63, 64, 65, 66, 68, 69, 70, 72, 74, 75, 76, 77, 78, 80, 81, 82, 84, 85, 86, 87, 88, 90, 91, 92, 93, 94, 95, 96, 98, 99, 100, 102, 104, 105, 106, 108, 110, 111, 112, 114, 115, 116, 117, 118, 119, 120, 121, 122, 123, 124, 125, 126, 128, 129, 130, 132, 133, 134, 135, 136, 138, 140, 141, 142, 143, 144, 145, 146, 147, 148, 150. Every composite number can be written as the product of two or more (not necessarily distinct) primes. For example, the composite number 299 can be written as 13 × 23, and the composite number
360360 may refer to: * 360 (number) 360 (three hundred sixty) is the natural number In mathematics, the natural numbers are those used for counting (as in "there are ''six'' coins on the table") and total order, ordering (as in "this is the ''thi ...
can be written as 23 × 32 × 5; furthermore, this representation is unique
up toTwo mathematics, mathematical objects ''a'' and ''b'' are called equal up to an equivalence relation ''R'' * if ''a'' and ''b'' are related by ''R'', that is, * if ''aRb'' holds, that is, * if the equivalence classes of ''a'' and ''b'' with respec ...
the order of the factors. This fact is called the
fundamental theorem of arithmetic In number theory, the fundamental theorem of arithmetic, also called the unique factorization theorem or the unique-prime-factorization theorem, states that every integer An integer (from the Latin wikt:integer#Latin, ''integer'' meaning "wh ...
. There are several known
primality test A primality test is an algorithm of an algorithm (Euclid's algorithm) for calculating the greatest common divisor (g.c.d.) of two numbers ''a'' and ''b'' in locations named A and B. The algorithm proceeds by successive subtractions in two loops: ...
s that can determine whether a number is prime or composite, without necessarily revealing the factorization of a composite input.

# Types

One way to classify composite numbers is by counting the number of prime factors. A composite number with two prime factors is a
semiprime In mathematics Mathematics (from Ancient Greek, Greek: ) includes the study of such topics as quantity (number theory), mathematical structure, structure (algebra), space (geometry), and calculus, change (mathematical analysis, analysis). It h ...
or 2-almost prime (the factors need not be distinct, hence squares of primes are included). A composite number with three distinct prime factors is a
sphenic numberIn number theory, a sphenic number (from grc, σφήνα, 'wedge') is a positive integer that is the product of three distinct prime number A prime number (or a prime) is a natural number greater than 1 that is not a Product (mathematics), pr ...
. In some applications, it is necessary to differentiate between composite numbers with an odd number of distinct prime factors and those with an even number of distinct prime factors. For the latter :$\mu\left(n\right) = \left(-1\right)^ = 1$ (where μ is the
Möbius function The Möbius function is an important multiplicative function :''Outside number theory, the term multiplicative function is usually used for completely multiplicative functions. This article discusses number theoretic multiplicative functions.'' ...
and ''x'' is half the total of prime factors), while for the former :$\mu\left(n\right) = \left(-1\right)^ = -1.$ However, for prime numbers, the function also returns −1 and $\mu\left(1\right) = 1$. For a number ''n'' with one or more repeated prime factors, :$\mu\left(n\right) = 0$. If ''all'' the prime factors of a number are repeated it is called a
powerful number A powerful number is a positive integer ''m'' such that for every prime number ''p'' dividing ''m'', ''p''2 also divides ''m''. Equivalently, a powerful number is the product of a Square number, square and a Cube (arithmetic), cube, that is, a numb ...
(All perfect powers are powerful numbers). If ''none'' of its prime factors are repeated, it is called Square-free integer, squarefree. (All prime numbers and 1 are squarefree.) For example, 72 (number), 72 = 23 × 32, all the prime factors are repeated, so 72 is a powerful number. 42 (number), 42 = 2 × 3 × 7, none of the prime factors are repeated, so 42 is squarefree. Another way to classify composite numbers is by counting the number of divisors. All composite numbers have at least three divisors. In the case of squares of primes, those divisors are $\$. A number ''n'' that has more divisors than any ''x'' < ''n'' is a highly composite number (though the first two such numbers are 1 and 2). Composite numbers have also been called "rectangular numbers", but that name can also refer to the pronic numbers, numbers that are the product of two consecutive integers. Yet another way to classify composite numbers is to determine whether all prime factors are either all below or all above some fixed (prime) number. Such numbers are called smooth numbers and rough numbers, respectively.

* Canonical representation of a positive integer * Integer factorization * Sieve of Eratosthenes * Table of prime factors

* * * * *