Drexel dragonThe Math ForumDonate to the Math Forum

Ask Dr. Math - Questions and Answers from our Archives
_____________________________________________
Associated Topics || Dr. Math Home || Search Dr. Math
_____________________________________________

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

    
Associated Topics:
High School Projects

Search the Dr. Math Library:


Find items containing (put spaces between keywords):
 
Click only once for faster results:

[ Choose "whole words" when searching for a word like age.]

all keywords, in any order at least one, that exact phrase
parts of words whole words

Submit your own question to Dr. Math

[Privacy Policy] [Terms of Use]

_____________________________________
Math Forum Home || Math Library || Quick Reference || Math Forum Search
_____________________________________

Ask Dr. MathTM
© 1994-2013 The Math Forum
http://mathforum.org/dr.math/