Prime Number 2001, Sieve of Eratosthenes

Date: 01/25/97 at 16:51:07
From: Davenports
Subject: 2001

Dear Dr. Math,

Please help us. Here is the problem that we are stuck on:

Is 2001 a prime number?

Thanks-
J and G

Date: 01/25/97 at 17:47:27
From: Doctor Wallace
Subject: Re: 2001

Hi J and G,

What an interesting question you have there!  Since you didn't say, 
I have no idea in what context this question comes up.  Maybe you 
are just curious?

Well, you might be interested to know that there is a branch of 
mathematics called number theory that deals with questions like this 
one.  Further, within number theory there is a mini branch of math 
called, you guessed it, prime number theory!  Most of its methods for 
determining if a number is or isn't prime are not magical, just very, 
very time consuming and "number crunching."  They are usually carried 
out by powerful, expensive computers.

The oldest I know of is called the Sieve of Eratosthenes. His method 
gives all the prime numbers less than any given integer n, by deleting 
from the set of all integers less than n the multiples of each of the 
primes up to the square root of n. For example, to find out whether 
1987 is prime, you only need to check that it is not divisible by 3, 
5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, and 43.  We can stop there, 
since the square root of 1987 is 44.57.  We only need to check primes 
because every integer can be factored into a unique product of primes.  
This is called its "prime factorization."

So what am I really suggesting to you?  You have to go trial and error 
number crunching.  But Eratosthenes says you only have to check the 
primes up to the square root of your number.  So for 2001, you may 
also stop with 43, because the square root of 2001 is 44.73.

So, have you tried all these primes to see if they go into 2001?  If 
you do it for 1987, you'll find out that 1987 is prime.  But is 2001?

Thanks for writing.  I hope this helps.  If you need more help, don't 
hesitate to write again!

-Doctor Wallace,  The Math Forum
 Check out our web site!