 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$.