×

How to Find Prime Numbers

••• Goodshoot/Goodshoot/Getty Images

Prime numbers are a mathematical concept that describes positive whole numbers that can only be divided evenly by two other whole numbers (or factors). For example, the number 2 is a prime number, because it can only be divided by itself and 1. Another prime number is 7. Prime numbers are important in many branches of mathematics, including cryptography, the making and breaking of codes.

The Hard Way

    Write down a number you wish to test to see if it is prime.

    Find the square root of the number you wish to test using a computer or calculator. If the square root is a whole number, then you know the number is not prime and can give up on it. Otherwise, the number could still be prime, so go on to step 3.

    Divide the number you are testing, one by one, by each number between 2 and the square root of the tested number. One of the traits of numbers is that, if they have a factor pair, one of the factors must be equal to or less than the square root. So, if you test all the numbers up to the square root, you can rest assured that the number is prime. For example, the square root of 23 is around 4.8, so you would test 23 to see if it can be divided by 2, 3 or 4. It cannot be, so 23 is prime.

    This solves the problem, but it is very labor intensive, especially when you wish to check a lot of numbers at once. For this reason, an ancient Greek mathematician created a method to make it easier.

Using the Sieve of Eratosthenes

    Decide on a range of numbers you wish to test and lay them out on square grid. Just like in the first method, you will need to find the square root to decide how wide to make the grid: your work will be shorter if the grid is as close to a perfect square as is possible.

    For example, to test all the numbers from 1 to 25 for primes, make the following 5x5 grid:

    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

    Cross out 1 with an X, because 1 is never considered prime by mathematicians for technical reasons.

    Circle 2, because 2 is a prime. Now, cross out with an X every number which can be evenly divided by 2. So, cross out 4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24. These numbers cannot be prime because they can be divided by a number other than 1 and themselves; namely 2.

    Circle 3, and repeat the previous step, crossing out all the multiples of 3 which aren't already crossed out.

    Skip 4, because it is crossed out and circle the next number which has not been crossed out (5). It is a prime number. Continue until all the numbers on your chart are either circled or crossed out. If you made your chart perfectly square, that should occur about the time you finish the first row.

References

About the Author

Kevin Walker is a computer programmer who decided to take a few years out from the corporate life and see the world. He spent a total of six years living abroad and teaching English in China, Korea and Mexico before returning to his home in Texas. He uses his programming and teaching experience to write easy-to-understand computer tutorials.

Photo Credits

  • Goodshoot/Goodshoot/Getty Images