Transcript document

Sieve of
Eratosthenes
By Tamika Allen, Frank Koegel,
and Kathleen Sylla
NSF Pedagogy Conference 2008
April 19, 2008
Eratosthenes of
Cyrene
(276 BC - 194 BC)
was a Greek
mathematician,
geographer, and
astronomer.
He is noted for devising a system of
latitude and longitude, and for being
the first known to have calculated
the circumference of the Earth.
He also created a map of the world
based on the available geographical
knowledge of the era.
A sieve is a utensil used to separate
solids from liquids or large particles
from small particles
The Sieve of Eratosthenes can be used
to filter out all numbers that are not
prime.
What is a prime number?
Number
Factors
5
1,5
Prime
6
1,2,3,6
Not Prime
Start with a certain set of whole
numbers, such as 1-20.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
Cross out 1 since it is not prime.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
Then begin with the next
number not crossed out. Cross
out all multiples of that number.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
Then go to the next number not
crossed out. That would be 3.
Cross out all multiples of that
number.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
Continue through each number.
What do you notice?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
So the prime
numbers between 1
and 20 are 2, 3, 5, 7,
11, 13, 17 and 19
What are the
primes to 100?
National Library of
Virtual Manipulatives
Prime Number Sieve
Sieve of Eratosthenes
Applet
Can you apply the
divisibility patterns?
Key:
multiples of 2
multiples of 3
multiples of 4
etc.
Lockers
A school’s lockers are numbered 1 to 100. One
hundred students enter the school one at a
time. The first student opens the lockers. The
second student closes the even-numbered
lockers. The third student either closes or
opens every third locker, and so on. After all
the students have passed the lockers, which
lockers are open?
The perfect squares!
1, 4, 9, 16, 25, 36, 49, 64, 81, 100
Sieve of Squares
Multiple Representations
• Using the hundred chart, we can:
– Filter the primes and composite numbers
– Apply divisibility rules
• Using students and counters, we can:
– Filter perfect squares
• We can even infuse technology…
• Sieve of Atkin
• Let’s play a game!
Sunshine State Standards
• MA.A.1.3 The student understands the
different ways numbers are
represented and used in the real world.
• MA.A.5.3 The student understands and
applies theories related to numbers.
• MA.D.1.3 The student describes,
analyzes, and generalizes a wide
variety of patterns, relations, and
functions.