Composite number

A composite number is an integer greater than one that is not a prime number. Equivalently, it has a factorization $n=ab$ with integers $a,b>1$. Thus $4=2\cdot 2$, $9=3\cdot 3$, and $12=3\cdot 4$ are composite numbers; one is neither a composite number nor a prime number.

Every composite number has a prime factor at most its square root. In $91=7\cdot 13$, seven is the smaller factor and lies below $\sqrt{91}$; in $49=7^2$, equality occurs. This square-root bound makes trial division finite and lets the sieve of Eratosthenes stop marking with prime numbers beyond $\sqrt{N}$ when listing prime numbers up to $N$.

A semiprime is a composite number that is a product of exactly two prime numbers, counted with multiplicity. For example, $6=2\cdot 3$ and $9=3^2$ are semiprimes. Distinct factors give $\phi (pq)=(p-1)(q-1)$ for the Euler totient function, whereas equal factors give $\phi (p^2)=p(p-1)$. This distinction matters when constructing a uniform coprime state for a semiprime.