2, 3, 5, 7, 11, 13, 17, 19...

Prime-Numbers.net

Where Prime Numbers mysteries are solved.

How do I Find Prime Numbers?

Finding a list of Prime Numbers

Finding a list of prime numbers can be done with the Sieve of Eratosthenes. This is a clever and visual way to eliminate composite numbers from a list. Say you want to find all the primes between 1 and 121, as the animate below depicts. What you want to do then is to draw out a grid with a spot for every number. First take 2. Highlight all the squares that have a factor of two, meaning all the even numbers. The next prime on the list is 3. Highlight all the numbers in the list that are a factor of 3. Do this for each prime number up until 11. The remaining numbers that are not highlighted will be prime!


The Sieve of Eratosthenes in action. Courtesy of Wikipedia.

Finding out if a number is prime

You may be interested only to check if one number is prime. If this is the case, you must check to see if the number is divisible by any primes up to the square root of the number. The reason you can stop at the square root of the number is because if there are numbers that are higher than the square root that divide the number, then it must be paired with a number lower than the square root. For example, if you wanted to check to see if 91 is prime, you would do the following:

  • Check to see if it's divisible by 2. It's not!
  • Check to see if it's divisible by 3. It's not! So far so good.
  • Check to see if it's divisible by 5. It's not! Let's keep going...
  • Check to see if it's divisible by 7. It is! 7 X 13 = 91.

Let's do another example where the number is prime. Let's do 97:

  • Check to see if it's divisible by 2. It's not!
  • Check to see if it's divisible by 3. Still ok.
  • Check to see if it's divisible by 5. Next!
  • Check to see if it's divisible by 7. Nope!

Since the next prime is greater than the square root of 97, it must be prime.