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