A Natural number $n > 1$ is prime if it has no [divisor_number_theory divisors] other than itself and $1$. Equivalently, it has the property that if $n \mid ab$ %%note:That is, $n$ divides the product $ab$%% then $n \mid a$ or $n \mid b$. Conventionally, $1$ is considered to be neither prime nor [composite_number 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.)
• Every natural number may be written as a product of primes; moreover, this can only be done in one way (if we count "the same product but with the order swapped" as being the same: for example, $2 \times 3 = 3 \times 2$ is just one way of writing $6$). (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 Sieve of Eratosthenes]. (There are other sieves available, but Eratosthenes is the simplest.)

There are many [primality_testing tests] for primality and for compositeness.

More general concept

This definition of "prime" is, in a more general ring-theoretic setting, known instead as the property of irreducibility. Confusingly, there is a slightly different notion in this ring-theoretic setting, which goes by the name of "prime"; this notion has a separate page on Arbital. In the ring of integers, the two ideas of "prime" and "irreducible" actually coincide, but that is because the integers form a ring with several very convenient properties: in particular, being a [euclidean_domain Euclidean domain], they are a Principal ideal domain (PID), and [pid_implies_ufd PIDs have unique factorisation].

[todo: add requisite for divisornumbertheory]