Deciding If a Number is Prime
As prime numbers have a number of applications (and because the ancient Greeks thought they were interesting), a great deal of work has gone into finding methods to determine whether a number is prime or composite.
The simplest such method is known as the Sieve of Eratosthenes, Eratosthenes being one of those ancient Greek mathematicians. Rather than checking to see if one particular number is prime, it simply finds all prime numbers up to a particular value.
The algorithm works as follows: first write down all the integers from two up to the largest number you'd like to check. Circle two: it is a prime number. Then go through the list and cross out every other number starting with four; because these are all multiples of two, they are all composite numbers. Circle the next number that is not crossed out; this is three, which is also prime. Now cross out every third number that isn't already crossed out. Six is crossed out, so we'll cross out nine, then twelve is crossed out so we cross out 15, and so on. Now go to the next number that isn't crossed out (five), circle it, and start crossing out every fifth number. Once you've passed the square root of the number you're interested in without crossing it out, you know that your number is prime.
This works because when you get to a number, you've already checked it against all prime numbers smaller than it, so nothing divides it; if it was divisible by a composite number, it would also be divisible by a prime. Every number that gets crossed out is a multiple of a prime and is thus composite.
This method is reasonably efficient for finding small primes. For checking whether large numbers are primes, advanced mathematical techniques are available. Additionally, there are ongoing searches to find the largest prime numbers that meet certain additional properties. For example, a Mersenne prime is a prime number of the form 2n-1; the largest known such prime so far is 243112609-1, which is a number much, much too large to actually type out; it contains nearly thirteen million digits!