Transcript THE SIEVE OF ERATOSTHENES: Prime and

THE SIEVE OF
ERATOSTHENES:
Prime and Composite Numbers
by Jan Harrison
http://ellerbruch.nmu.edu/classes/CS255W04/cs255students/jharriso/P12/P12.html
Eratosthenes
Eratosthenes was a Greek scholar who
lived in the 3rd century B.C. During his
life, he made many important
contributions to the fields of
mathematics, geography, philosophy, and
astronomy.
Among his contributions to mathematics (over
2,000 years ago), Eratosthenes is particularly
well known for:
Calculating a
surprisingly accurate
measurement of the
Earth’s circumference.
Devising the Sieve of
Eratosthenes, a tool for
finding prime numbers.
Prime Numbers
A number is regarded as prime only if it
has exactly two factors: 1 and itself.
For example:
The number 2 has exactly two factors: 1 and itself (i.e.,
1 and 2); therefore, it is a prime number.
Composite Numbers
If a number is not prime, then it is
composite.
For example:
The number 12 has six factors: 1, 2, 3, 4, 6, and itself
(i.e., 1, 2, 3, 4, 6, 12); therefore, it is a composite
number.
The number 1:
is neither prime nor
composite.
Why do you think
this is? [Hint: Look
back at the definition of a prime number.]
Prime or Composite?
Is the number 22 prime or composite?
Why?
What about the number 39?
7?
77?
The answers:
22 is a composite number, as it has
more than two factors (1, 2, 11).
39 is a composite number, as it has
more than two factors (1, 3, 13).
7 is a prime number, as it has only two
factors (1, 7).
77 is a composite number, as it has
more than two factors (1, 7, 11).
2 is the only even prime number.
Why?
Building Blocks
Have you noticed that the factors of
composite numbers are always prime
numbers? The Fundamental Theorem of
Arithmetic states that every natural number
greater than 1 has one unique way of being
represented as a product of its prime
factors. For this reason, the prime numbers
are sometimes called the “building blocks” of
the natural numbers.
Finding Prime Numbers
The Sieve of Eratosthenes is a tool that
will help you find prime numbers.
[Note: A worksheet is available at the web page for this lesson,
if you want to try this as you read along.]
The Sieve of Eratosthenes generally
looks something like this (depending
on the range of numbers included):
Image borrowed from
http://educ.queensu.ca/~fmc/dece
mber2003/Sieve.html
How to use the Sieve of
Eratosthenes:
1)
2)
3)
4)
Since the number 1 is neither prime nor composite, draw a box
around 1.
Circle the first unmarked number, 2, which is the first prime
number. Then count by 2, crossing out each multiple of 2 (i.e.,
cross out 4, 6, 8, etc.—the rest of the even numbers).
Circle the next unmarked number, 3. Then count by 3,
crossing out each multiple of 3 that has not already been
crossed out (i.e., 9, 15, 21, etc.).
Continue in this manner, circling primes and crossing out
composites, until you are done sieving.
Sieved-out Prime Numbers
After you are done sieving, any numbers
that remain (have not been crossed out)
are prime numbers. Do you see any
patterns in the Sieve of Eratosthenes?
Patterns
One of the educational advantages of
the Sieve of Eratosthenes is that it
helps to develop your ability to see and
extend patterns. Note the even
numbers, for example. Do you see an
actual pattern reflected in the table?
What about multiples of 5?
Other ways to mark the prime
and composite numbers:
Circling and crossing off numbers is just one
way to mark the prime and composite numbers
in a Sieve of Eratosthenes. Some people
color-code the numbers (e.g., marking the
multiples of 2 in red, 3 in green, etc.), as in
the earlier illustration. This helps them to
find and analyze patterns. Can you think of
other ways that you might mark the primes
and composites?
Now that you’ve learned about the Sieve
of Eratosthenes, do you see an error in
this one shown to you earlier?
Just for fun (after trying the worksheet), check out
one or more of the following sites and their interactive
activities relating to primes and/or the Sieve of
Eratosthenes:
Sieve of Eratosthenes:
http://matti.usu.edu/nlvm/nav/frames_asid_158_g_4_t_1.html?open=instructions
http://www.win.tue.nl/~ida/demo/c1s4ja.html
http://ccins.camosun.bc.ca/~jbritton/sieve/jberatosapplet.htm
Prime Number List
http://ccins.camosun.bc.ca/%7Ejbritton/jbprimelist.htm
Prime Factorization Machine
http://ccins.camosun.bc.ca/%7Ejbritton/jbprimefactor.htm
Sites to explore for more information
on primes or Eratosthenes:
The Prime Pages (University of Tennessee—Martin)
http://www.utm.edu/research/primes
Prime Numbers
http://www.factmonster.com/ipka/A0876084.html
World’s Largest Known Prime Number
http://www.factmonster.com/ipka/A0920820.html
Eratosthenes of Cyrene (University of St. Andrews)
http://www-history.mcs.stand.ac.uk/history/Mathematicians/Eratosthenes.html
THE END