Prime Number

A prime number is a number that is evenly divisible by no other number except for itself and 1. A number which is not prime is called a composite number. The classifications prime and composite apply to positive integers greater than 1, though there are related concepts in other fields of mathematics. Note that 1 is neither prime nor composite.

The smallest prime numbers are 2, 3, 5, 7, 11, 13... . An exmple of a composite number is 6, which is evenly divisible by both 2 and 3.

It is easy to prove that there are an infinite number of primes. If there were a finite number of primes, you could multiply them all together and add 1. The resulting number would show the existence of a new prime, since it would not be divisible by any smaller prime (it would always have a remainder of 1).

To construct a table of prime numbers, you would use a method called the Sieve of Eratosthenes. Simply write down an ordered list of all counting numbers greater than 1. Beginning with 2*2 = 4, cross out every second number:

2 3 4 5 6 7 8 9 10 11 ...

then beginning with 3*3 = 9 cross out every third number:

2 3 4 5 6 7 8 9 10 11 ...

Beginning with 5*5 = 25, cross out every fifth number, then repeat for the primes 7, 11, 13, etc. The result will be a table of primes which is accurate up to n-squared, where n is the largest number you sieved for.

Primality testing

To determine whether a number is prime, you can use the trial division method, provided the number you are testing is not too large. Let N be the number being tested and s be its square root. Divide N by each number in the prime table, beginning with 2. If there is no remainder, stop--N is composite. Otherwise, test again with the next largest prime in the table. If the next largest prime is greater than s, stop--N is prime.

For larger values of N, a method based on Fermat's theorem can be used, though it usually requires a computer. Start with the number 1, and double it N-1 times. Divide this number by N, keeping only the remainder. If the remainder is greater than 1, N is composite. Unfortunately, the converse is not true--if the remainder is 1, N is probably prime, but not necessarily. Algorithms which improve on this method exist, and primality testing is today an active subject of mathematical research.