Last week we talked about what a prime number is, but we didn't talk about a good way of finding what number is prime and what is not (other than checking if any number less than p divides that number). This area of finding out what number is prime has been a big problem for many mathematicians and still has a lot of unanswered questions. The world of mathematics is still looking for an easy way to calculate whether a number is prime or not with a simple formula.
There are a few ways of finding primes, but the simplest (and one of the oldest) ways to finding a prime is by using a process called 'the sieve of Eratosthenes'. Take out a piece of paper and make 10 rows and 10 columns and number them in order from 1 to 100. Row 1 should have the numbers 1-10 in order, row 2 should have 11-20 in order, etc. Then, starting from 2, cross out all the numbers that 2 divides without crossing out 2 (e.g. 4, 6, 8, 44, 96). Then go to the next number and cross out all the number that it divides without crossing that number out. (The next number is three so cross out 9, 15, 21, etc.) Then go to the next number not crossed out and cross out all the numbers that it divides without crossing that number out. (5 is the next number so we cross out 25, 35, 55, etc.) We keep going until we find all the primes less than 100. Write down all the numbers in order, and you'll notice you have the same list that I listed last week! Cool! And that is basically the whole concept behind the sieve of Eratosthenes. You write down all the numbers and you go prime by prime removing all the ones that are not prime by going number by number. So if you wanted to find all the numbers less than 1,000 you would draw a 100 x 100 table of numbers and cross out each one as it came. This can be very time consuming! That's why mathematicians, didn't stop there.
A second way to see if a number is prime is to use what mathematicians like to call Wilson's Theorem. This theorem states that if p is prime then 
(Remember modulo? We're basically saying the remainder when you divide p from (p-1)! +1 is 0.) And the theorem goes vice versa, so that if a number that is not prime is placed into the equation the remainder/modulo will not be 0. Kinda handy for looking at medium size numbers!
Another way of finding primes is to find what are called Mersenne primes. These primes were talked about by a French monk Marin Mersenne from the 17^th^ century. They are primes of the form 
where 
is the m^th^ Mersenne number. It turns out that this is a good way to find other primes. If the m^th^ Mersenne number is prime the m is also prime. The issue is that this is a little cumbersome and doesn't work in reverse (If m is prime it does not mean 
is prime too.)
There are more complex ways of finding primes, but those are some of the most interesting and easy ones. Have a suggestion? Add a comment!