A prime number is a natural number (i.e., the counting numbers: 1, 2, 3, 4…), greater than 1, that has no divisors except 1 and itself. For example, 5 is prime because no numbers divide into it evenly except 1 and 5. The number 4 is not prime, because in addition to 1 and 4, it can be divided evenly by 2. Numbers that are not prime are called composite numbers.
The most basic method of checking whether or not a number is prime (a property called primality) is called trial division. Basically, this consists of dividing the number (we’ll call it n) by every integer (or whole number) that is greater than 1 and less than or equal to the square root of the number. If any of these divisions results in an integer, then n is not a prime. So, using a small number as an example, to test if 13 is a prime number, we would divide it by all integers from 1 to 3 (the square root of 13 is around 3.6). None of these divisions result in an integer, so 13 is prime.
Another method for finding all primes up to a given number, is called a prime number sieve. The oldest example is the sieve of Eratosthenes (shown in the animated gif below). This sieve is useful for relatively small primes. To make your own sieve of Eratosthenes up to 100, start with a number grid up to 100 (10 row, with 10 numbers in each row row).
- Cross out 1, since prime numbers must be greater than 1.
- The first prime number is 2. Cross out all multiples of 2 (the even numbers).
- The next prime number is 3. Cross out all multiples of 3 (in other words, count by three’s: 3, 6, 9, 12…).
- The next prime is 5 (4 has already been crossed out). Cross out all multiples of 5.
- The next number remaining is 7 (the next prime). Cross out all remaining multiples of 7.
- All remaining numbers are prime numbers. (No other numbers have multiples below 100 that have not already been crossed out.)
You can download my worksheet with these instructions and a grid here.
You may have read something about prime numbers in the news recently. The largest known prime, was discovered by a mathematician at University of Central Missouri, Curtis Cooper. This newly discovered prime number is 17,425,170 digits long! Of course, finding primes this large require powerful computers and algorithms more advanced than the sieve above, but I’ll leave that for a future post.