Prime and Composite Numbers, Sieve of Eratosthenes

Date: 01/28/97 at 16:35:06
From: Richard J. Principe
Subject: Prime numbers and composite numbers

I need to come up with a list of all prime numbers and all composite 
numbers up to 50.  Can you help me?  

Thank you very much.
Valerie 

Date: 02/02/97 at 15:36:44
From: Doctor Reno
Subject: Re: Prime numbers and composite numbers

Hi there, Valerie!

Before we talk about prime numbers, I want to review some 
multiplication vocabulary with you...

Let's look at the multiplication problem 5 x 6 = 30. 

   The 5 and 6 are called factors. They are the numbers we multiply 
   together. 

   The answer 30 is called the product. 30 is also called a multiple 
   of 5 because it is a product of 5 and another number, 6. 
   30 is also a multiple of 6 because it is the product of 6 and 5. 

   The number 5 has many other multiples, like 10, 15, 20, 25, 35, 
   40, etc. The number 6 also has many other multiples, like 12, 18, 
   24, 36, 42, etc. 

   Notice that multiples are the "times tables" for a number. 
   30 is a multiple of not only 5 and 6, but also of 2 (2x15), 
   3 (3x10), 10, and 15.

A prime number is a numbers greater than one whose factors are only 
one and itself. In other words, 6 is not prime, because its factors 
are 1,2,3, and 6 (1x6, 2x3). But 5 is prime, because the only way you 
can get a product of 5 is by multiplying 1 and 5 (1x5). 

Composite numbers are all the other positive numbers greater than one. 
6 is composite.

The number one is not prime OR composite because it has only one 
factor. 

Mathematicians have been fascinated by prime numbers for thousands of 
years. In fact, Eratosthenes (275-194 BC, Greece), devised a "sieve" 
to discover prime numbers. A sieve is like a strainer that you drain 
spaghetti through when it is done cooking. The water drains out, 
leaving your spaghetti behind. Eratosthenes's sieve drains out 
composite numbers and leaves prime numbers behind! You can use the 
sieve to find the prime numbers up to 100 (so you'll be ready for your 
teacher's *next* question!). 

To do what Eratosthenes did, make a chart of the first one hundred 
whole numbers (1-100):

            The Sieve of Eratosthenes
 
      1   2   3   4   5   6   7   8   9  10
     11  12  13  14  15  16  17  18  19  20
     21  22  23  24  25  26  27  28  29  30
     31  32  33  34  35  36  37  38  39  40
     41  42  43  44  45  46  47  48  49  50
     51  52  53  54  55  56  57  58  59  60
     61  62  63  64  65  66  67  68  69  70
     71  72  73  74  75  76  77  78  79  80
     81  82  83  84  85  86  87  88  89  90
     91  92  93  94  95  96  97  98  99 100

Next, cross out 1, because it is not prime.

Then circle 2, because it is the smallest positive even prime. Now 
cross out every multiple of 2..; in other words, cross out every 2nd 
number.

Then circle 3, the next prime. Then cross out all of the multiples of 
3; in other words, every third number. Some, like 6, may have already 
been crossed out since they may be multiples of 2.

Then circle the next open number, 5. Now cross out all of the 
multiples of 5, or every 5th number.

Continue doing this until all the numbers through 100 are either 
circled or crossed out!

And now, Valerie, if you have remembered your multiplication tables, 
you have just circled all the prime numbers less than 100!

Computer people have written computer programs that do this same sieve 
of Eratosthenes. They use the sieve to test computers and to tell them 
how much faster one computer runs than another computer. You don't 
have to stop the sieve at 100 - you can go up as far as you want to 
find all the prime numbers you want to find. But, as you found, there 
is a lot of multiplication involved. That is why computers are now 
used to find prime numbers.

To learn more about all sorts of prime numbers, go to:

  http://www.astro.virginia.edu/~eww6n/math/PrimeNumber.html   

This page has some very difficult stuff on it, but at the end there 
are links to other primes and their properties.

Take care, and have fun finding your prime numbers.

-Doctor Reno,  The Math Forum
 Check out our web site!  http://mathforum.org/dr.math/