A natural number $n>1$ is prime if it has no divisors other than itself and $1$. Equivalently, it has the property that if $n\mid ab$ ^[1] then $n\mid a$ or $n\mid b$. Conventionally, $1$ is considered to be neither prime nor composite (i.e. non-prime).

Examples

• The number $2$ is prime, because its divisors are $1$ and $2$; therefore it has no divisors other than itself and $1$.
• The number $3$ is also prime, as are $5,7,11,13,\dots$.
• The number $4$ is not prime; neither are $6,8,9,10,12,\dots$.

Properties

• There are infinitely many primes. (Proof.)

How to find primes

If we want to create a list of all the primes below a given number, or the first $n$ primes for some fixed $n$, then an efficient way to do it is the Sieve of Eratosthenes. (There are other sieves available, but Eratosthenes is the simplest.)

There are many tests for primality and for compositeness.

1. ^{^︎}

   That is, $n$ divides the product $ab$