A natural number is prime if it has no divisors other than itself and . Equivalently, it has the property that if [1] then or . Conventionally, is considered to be neither prime nor composite (i.e. non-prime).
If we want to create a list of all the primes below a given number, or the first primes for some fixed , 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.
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, they are a principal_ideal_domain (PID), and PIDs have unique factorisation.
That is, divides the product