prime number

A positive whole number (i.e., a natural number) is said to be prime if it has no proper divisor other than 1.

It is common for primes to be defined as numbers “divisible only by themselves and 1.” This definition, however, would make the number 1 itself prime, and this is incorrect; 1 is neither prime nor composite. Thus, the primes begin with 2, and continue with 3, 5, 7, 11, 13, etc.

To identify primes one may use the Sieve of Eratosthenes: first strike out every multiple of 2, then every multiple of 3, then 5, 7, and so on. By striking out all the numbers divisible by any prime up to \(n\), we are assured (by the Fundamental Theorem of Arithmetic) that every remaining number up to \(n^2\) is a prime number. Equivalently, one may test whether a given number \(m\) is prime by dividing it by every prime less than or equal to \(\sqrt{m}\). If any such divides it evenly, then it is not prime, and otherwise it is prime. There are faster ways than this ancient method for determining whether a given number is prime, but no method is known that is much faster, especially for very large prime numbers.

There are twenty-five primes between 1 and 100, but only eight in the last 100 integers before 100,000. It has been known since Euclid that there is no largest prime number, although the average proportion of primes in any given stretch of numbers of a consistent length becomes arbitrarily small. The Prime Number Theorem makes this precise.