Finding Prime Numbers

Date: 11/22/95 at 15:37:30
From: Wayne Davidson
Subject: Prime Numbers

Dear Sirs,

	I am writing to you about a question I have about prime numbers.  
I know that by definition a prime number is a number that will not 
divide evenly into any number except for 1 and itself.  I am currently 
working on a computer program in Turbo Pascal that finds prime numbers.  
I am doing this by dividing the number by every integer between 1 and 
itself-1.  I would like to know if I would get the same exact answers if 
I were to test the numbers only between 2 and the square root of the 
number?  

	For example if I was checking the number 100 (obviously 100 is 
composite, but I am just using it for simplicity), I would check every 
number between 2 and 10, inclusive, instead of checking every number 
starting at 2 and ending with 99.  Would I get the same answer? 

	This has been suggested to me by my math teacher but I am not 
quite sure what he was saying and I can't ask him now because 
unfortunately he is in the hospital recovering from open-heart 
surgery.  

			Thank for your help,

					Joe Davidson

Date: 11/27/95 at 12:42:30
From: Doctor Eric
Subject: Re: Prime Numbers

Wayne,

    Your teacher was right.  In fact, there's an even more specific set 
of numbers that you can use, but let's first figure out what he meant.  
Why stop at the square root?  Do you see how the square root kind of 
forms a middle point for divisors of the number?  To get the desired 
number, you'd have to multiply one number smaller than it's square root, 
and one bigger.  So to test numbers about the square root would be 
redundant!

    Now, what's even more interesting is that you don't even need to 
check every integer between 2 and the square root of the number.  I 
propose that it suffices to only check PRIME numbers between 2 and the 
square root.  Can you figure out why?  As far as the programming goes, 
this would involve somehow keeping track of the primes that you've found 
so far, and then only dividing your next test number by those in this 
list that are smaller than the square root of the number.

     If you have a Web browser, you may benefit from taking a look at 
the following page:

Finding Primes, http://www.utm.edu/research/primes/proving.html   

-Doctor Eric,  The Geometry Forum