Prime numbers are an important concept in Number Theory and Cryptography which often uses the difficulty of finding prime numbers as a basis for building encryption systems that are difficult to break without going through all (or a very large number of) possible choices.
Remember that a prime number is a number greater than 1 whose only divisors are 1 and that number itself. One of the most famous algorithms for searching for prime numbers is the Sieve of Eratosthenes. I added a script which implements the Sieve of Eratosthenes to my Examples page.
This algorithm prints out all prime numbers less than a given number by first canceling out all multiples of 2 (the smallest prime), then all multiples of 3 (the second smallest prime), then all multiples of 5 (the third smallest prime – multiples of 4 do not need to be considered because they are also multiples of 2), etc until we have reached a number which cannot be a divisor of this maximum number.
So if we are given a number, n, the first step of the algorithm is write out a table that lists all the numbers that are less than n. For example lets run this Sieve on 50. So all numbers less than 50 are
1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50.
So since 1 is not a prime number (by the definition of prime numbers), we cancel that number out.
1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50.
Next, we look at the list and the first number that is not crossed out is a prime. That number is 2. We will put a mark by 2 and cancel out all of 2’s multiples.
1, 2*, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50.
Again, we look at the list and the first number that is not marked or crossed out is 3, so that number is prime. We will put a mark by 3 and cancel out all of 3’s multiples.
1, 2*, 3*, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50.
Once again, we look at the list and the first number that is not marked or crossed out is 5, so that number is prime. We will put a mark by 5 and cancel out all of 5’s multiples.
1, 2*, 3*, 4, 5*, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50.
We look at the list and the first number that is not marked or crossed out is 7, so that number is prime. We will put a mark by 7 and cancel out all of 7’s multiples.
1, 2*, 3*, 4, 5*, 6, 7*, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50.
Now, we look and the first number that is not crossed out is 11. However, since 11 is greater than sqrt(50) we know that each of 11’s multiples that are less than 50 will have been cancelled out by a previous prime number. So we have finished the algorithm.
Check out my script which implements the Sieve of Eratosthenes for more examples.