Transcript Sieve of Eratosthenes

The Sieve of
Eratosthenes
“Finding Prime Numbers”
By: Patt Hawkey, MS
Vocabulary Used with Primes
Composite
 Divisibility
 Divisible
 Even
 Even Number
 Factor
 Factorization
 Factor pair
 Factor tree

GCF
 LCM
 Multiple
 Odd
 Odd Number
 Prime
 Prime Factorization
 Test

What is a Sieve?
A colander or “sifter”
often used in cooking.
 The Sieve of
Eratosthenes “Sifts”
the numbers put into it
to remove the
multiples or the
composite numbers
and leaves the prime
numbers.

A Sieve
In Action!
Who Was
Eratosthenes of Cyrene
 He
was a mathematician
 Lived in 275 to 195 B.C.
 First to estimate accurately the diameter
of the earth.
 Developed an interesting way of locating
prime numbers which we call the:
 Sieve
of Eratosthenes
Counting or Natural Numbers
 These
are numbers starting at 1
 They can be classified as either a Prime or a
Composite number.
A
Prime Number is a number greater than one
that has exactly 2 factors -Itself and one
 A Composite Number has more than 2 factors
 NOTE:
Mathematicians decided, many years
ago, that the number 1 will NOT be
considered neither prime nor composite
Prime Factorization

Every natural number that is composite has only one
prime factorization. For example:
Hawkey Stick
Factor Tree
Method
12
12
2
2
6
2
2 x 2 x 3
2
6
3
3
2 x 2 x 3
The Sieve of Eratosthenes Method
 It
uses a hundreds chart where we
will cross out the multiples with
different colored pencils.
 By counting by multiples to eliminate
the composite numbers we will be left
with only the primes on the chart.
 Remember to look for patterns as you
find the multiples or the composite
numbers.
Sieve of Eratosthenes
1
11
21
31
41
51
61
71
81
91
2
12
22
32
42
52
62
72
82
92
3
13
23
33
43
53
63
73
83
93
4
14
24
34
44
54
64
74
84
94
5
15
25
35
45
55
65
75
85
95
6
16
26
36
46
56
66
76
86
96
7
17
27
37
47
57
67
77
87
97
8
18
28
38
48
58
68
78
88
98
9
10
19 20
29 30
39 40
49 50
59 60
69 70
79 80
89 90
99 100
For this activity you will need:
100
chart
Colored Pencils or Crayons:
black
red
green
blue
yellow
Finding the Primes
Step #1
Cross
out in black the number
one (1) - because it isn’t prime.
Circle the number 2, the first
prime and using red cross out
all of the multiples of 2
Finding the Primes
Step # 2
Circle
the number 3 then using
green cross out all of the
multiples of 3
Circle the number 5 then using
blue cross out all of the
multiples of 5
Finding the Primes
Step # 3
Circle the number 7, then using
yellow cross out all of the
multiples of 7
Circle
all of the remaining
numbers that are not crossed out.
They are prime numbers.
Sieve of Eratosthenes
25 Primes < 100
1
11
21
31
41
51
61
71
81
91
2
12
22
32
42
52
62
72
82
92
3
13
23
33
43
53
63
73
83
93
4
14
24
34
44
54
64
74
84
94
5
15
25
35
45
55
65
75
85
95
6
16
26
36
46
56
66
76
86
96
7
17
27
37
47
57
67
77
87
97
8
18
28
38
48
58
68
78
88
98
9
19
29
39
49
59
69
79
89
99
10
20
30
40
50
60
70
80
90
100
Questions
1.
2.
3.
Why didn’t we cross out multiples of 4
and 6?
• Because they are multiples of 2
Did we need to cross out the multiples
of 8, 9 or 10?
• NO, because they are multiples of 2
and 3
What is the next prime number after
7?
• 11
Questions
4.
5.
What number do we get when we
square that number?
• 121
Why could we stop after we crossed
out multiples of 7?
• Because the square of 7 is 49 and 11
squared is 121 more than 100
Assignment
 Answer
the 17 questions on primes:
“Prime Findin’”
Bibliography







http://www.math.utah.edu/~pa/Eratosthenes.html History
and animation of the Sieve of Eratosthenes
http://www.math.utah.edu/classes/216/assignment-07.html
http://www.faust.fr.bw.schule.de/mhb/eratosiv.htm
Interactive animation of primes < 400
http://www.mathnstuff.com/papers/games/prime.htm Prime
Factor game
http://www.research.att.com
http://mathworld.wolfram.com
http://mathforum.org - Ask Dr. Math