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.

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
Math Forum Home || Math Library || Quick Reference || Math Forum Search