Finding Prime Numbers

This post first appeared at kkdegner@blog.com on 7/22/13.

Last week I came across this little doozy on my Facebook page, which was posted by The Belin Blank Center, which it looks like they must have reposted from the National Council of Teachers of Mathematics

Screen Shot 2013-08-13 at 10.24.28 AM

I love the question for so many reasons!  First, I love it because its not complicated.  If you know what a prime number is and you know how to find square roots, you’re set!  Trial and error might be the weapon of choice for many people answering this question.  And while there’s nothing particularly wrong with trial and error, it can take a while and, well, its not really that interesting.  But, we could use just a little, tiny bit of strategy to try to cut down on the amount of numbers we have to test in order to answer the question.

To address this question we have to check 3 things 1)is the number prime? 2) is the square root less than 20? 3)is there a larger prime number whose square root is also less than 20?  Let’s start by setting an upper bound to eliminate the 2nd and 3rd questions.  We know that 20 squared is 400, meaning all numbers less than 400 have a square root less than 20.  So now we know we’re looking for prime numbers which are less than 400.  If you’re feeling very adventurous, you could just list all of the numbers between 1 and 400.  The largest prime in that list of numbers would be the answer to the question.  But, do you really want to check 399 numbers too see if they’re prime? No?  Me neither.  (We don’t have to check 1, we know its not prime or composite).

Good news!  We can use our knowledge of numbers and their factors to whittle this list down pretty quickly!  First, get rid of all the even numbers (except for 2–its prime), because we know they’re divisible by 2.  Additionally, get rid of all of the numbers ending in 5 (except for 5–prime!), because they’re divisible by 5.  Now we’re down to, what 161 numbers by my count?  That still seems like a lot of numbers to test, no?  There are still other numbers we could systematically check off of our list of possibilities, for example the multiples of 11 and 3 are pretty easy to spot (prime and prime, respectively).  Taking the grand total of possibilities down to 105 numbers.

photo[1] copy

From here, we could do a few things.  Starting with the largest number left on the list (the largest number I have left is 397), we could check to see if the number is prime.  If it is, then great!  We’ve found the answer. If you don’t like that method we could continue along the path we’ve been on.  That is, now cross out all of the multiples of 7, 13, 17, and 19.  See what’s left standing, check to make sure that its prime and just for fun, calculate an approximation of the square root.  Happy Number Crunching!

Wait, you didn’t think I’d actually give you the answer, did you?  What would be the fun in that?  I’ll tell you what I will do though, I’ll tell you about a little tool/algorithm/rule that is very helpful in answering this question (and its one I’ve been using in this post).  Its called the Sieve of Eratosthenes and it says this:

List all of the numbers from 1 – n (in our case 400).  To find all of the prime numbers, start with the smallest prime (2) and cross out every second number in your list.  Now, go to the next number in the list that you haven’t crossed out (3).  Cross out every 3rd number (notice, some of the numbers like 6 and 12 in your list you will have now crossed out twice).  Continue this process through all of the numbers 1 – square root of (n).  The numbers remaining are all of the prime numbers 1 – n.  

Now you can answer that nice little problem!

What’s that you say?  You don’t understand why 1’s not a prime number?  Don’t worry, you wouldn’t be the first to ask.  Have you ever heard of Math Warriors?  Felicia does a great job of explaining this question in this episode.  (If you haven’t seen Math Warriors yet, you might as well just start at the beginning by going here.)

P.S. I included lots of great math resources in this post.  Follow them on Facebook and Twitter!

BBC Facebook                              BBC Twitter @belinblank

Math Warriors Facebook         Math Warriors Twitter @MathWarriors

NCTM Facebook                         NCTM @NCTM

Sources:

Weisstein, Eric W. “Sieve of Eratosthenes.” From MathWorld–A Wolfram Web Resource. http://mathworld.wolfram.com/SieveofEratosthenes.html

Advertisements