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]