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
Search the Dr. Math Library:
Ask Dr. MathTM
© 1994- The Math Forum at NCTM. All rights reserved.