Transcript 03 Sieve of Eratosthenes

Slides for Chapter X
Note to Instructors
This Keynote document contains the slides for “The Sieve of Eratosthenes”, Chapter 3 of
Explorations in Computing: An Introduction to Computer Science.
The book invites students to explore ideas in computer science through interactive tutorials where
they type expressions in Ruby and immediately see the results, either in a terminal window or a 2D
graphics window.
Instructors are strongly encouraged to have a Ruby session running concurrently with Keynote
in order to give live demonstrations of the Ruby code shown on the slides.
License
The slides in this Keynote document are based on copyrighted material from Explorations in
Computing: An Introduction to Computer Science, by John S. Conery.
These slides are provided free of charge to instructors who are using the textbook for their courses.
Instructors may alter the slides for use in their own courses, including but not limited to: adding new
slides, altering the wording or images found on these slides, or deleting slides.
Instructors may distribute printed copies of the slides, either in hard copy or as electronic copies in
PDF form, provided the copyright notice below is reproduced on the first slide.
© 2012 John S. Conery
The Sieve of Eratosthenes
An algorithm for finding prime numbers
✦
The Sieve Algorithm
✦
The mod Operator
✦
Containers
✦
Iterators
✦
Boolean Values
✦
Exploring the Algorithm
✦
A Better Sieve
✦
Experiments with the Sieve
Explorations in Computing
© 2012 John S. Conery
History
✦
✦
Prime numbers have a long and interesting history
❖
a number is prime if it cannot be written as the product of two smaller numbers
❖
non-prime numbers are called composite numbers
❖
these are primes: 5, 11, 73, 9967, ...
❖
these are composite: 10 (2 × 5), 99 (3 × 3 × 11), ...
Ancient Greek, Persian, and Chinese philosophers all studied properties of
prime numbers
❖
the Sieve of Eratosthenes, the algorithm
we’re looking at today, is one of the
oldest known algorithms
❖
dates to at least 200 BC
See http://primes.utm.edu
Motivation
✦
Until the middle of the 20th century prime numbers were of interest only to
number theorists
✦
In 1970 a new method for encrypting messages was invented
❖
the security of the RSA algorithm
relies on the difficulty of finding
the factors of large numbers
❖
here “large” means numbers
with 500 digits or more
❖
RSA has renewed interest in
properties of prime numbers
and methods for generating
them
Big Number
UCLA
✦
✦
In Aug 2008 a project named
GIMPS (Great Internet
Mersenne Prime Search)
set a new record
❖
the largest known prime
number is now 243112609 - 1
❖
around 13 million digits
❖
the group that found it
claimed a $100,000 prize....
At 10 digits/inch:
❖
12” thick book, or
❖
a string 20 miles long
“The Dinette Set” by Julie Larson
The Sieve
✦
The basic idea is simple:
make a list of numbers, starting with 2
repeat:
the first number in the list is prime
cross off multiples of the most recent prime
See “Sieve of Eratosthenes” at Wikipedia
Technology
✦
The method described on the previous slide works well for short lists
✦
But what if you want to find prime numbers between 2 and 100? 1000?
✦
❖
it’s a tedious process to write out a list of 100 numbers
❖
takes a lot of paper to make a list of 1000 numbers
❖
chances are you will make a few arithmetic mistakes (this is a boring job)
You could improve accuracy by using an abacus or calculator
❖
but it’s still very boring....
Technology (cont’d)
✦
Can we turn this method into a computation?
❖
✦
detailed specification of starting and ending conditions are there
What about the steps?
❖
“cross off” and “next number” need to be defined if we’re going to use Ruby
❖
when do we stop the process? when all the numbers are crossed off?
Isn’t is “obvious” there are no multiples of 11 in this list?
We don’t have to cross off all the
numbers -- we can stop when
there are still numbers left
A Ruby Method
✦
The project for this chapter: a Ruby program that implements the Sieve of
Eratosthenes
✦
Two goals: non-trivial example of computation, more Ruby skills
✦
What we’ll see in this project this:
❖
how to work with lists of numbers in Ruby
❖
how to write an expression that repeats an operation (e.g. looking through the list for prime
numbers)
Divisibility
✦
An important question: how do we determine whether or not to remove a
number from the list?
✦
Useful fact: if a number x is the product of two numbers n and m then
✦
✦
❖
the remainder of x ÷ m is 0
❖
the remainder of x ÷ n is also 0
Example:
❖
77 is not prime because 77 = 7 × 11
❖
77 ÷ 7 = 11 R 0
❖
77 ÷ 11 = 7 R 0
So the way to implement the step that deletes multiples:
❖
remove any number x if the remainder of x ÷ p is 0 (where p is the most recent prime)
The Mod Operator
✦
Ruby has a very useful arithmetic operator for this step:
x % y is the remainder after dividing x by y
✦
Examples:
>> 10 % 3
=> 1
>> 77 % 10
=> 7
>> 77 % 11
=> 0
>> 77 % 7
=> 0
10 % 3
is pronounced
“ten mod three”
Modulo Arithmetic
✦
This new operator is called the “mod” operator
❖
✦
✦
based on the “modulo” function of number theory
Mathematicians usually write the name of the operator instead of a symbol
❖
77 mod 10 = 7
❖
77 mod 11 = 0
Modulo arithmetic is often introduced
as “clock arithmetic”
❖
if it’s 8 o’clock now, what time will
it be 30 hours from now?
❖
8 + 30 mod 12 = 2
❖
in Ruby:
>> (8 + 30) % 12
=> 2
A Useful Operation
✦
The mod operator is a surprisingly useful operation
❖
✦
✦
we’ll see it again in several projects this term
For this project, the main use will be to test divisibility
❖
suppose p is a prime number (one of the numbers we’ve already “circled”)
❖
let x be one of the numbers left on the list
❖
we’ll remove x from the list if x % p is 0
Next topic: how to make the lists of numbers
Aside: Containers
✦
✦
In everyday life we often encounter collections
❖
course catalog -- collection of course descriptions
❖
car lot -- collection of cars
Mathematicians also work with collections
❖
matrix
❖
sequence (e.g. 1, 1, 2, 3, 5, 8, ...)
✦
In computer science we make a collection by defining a “data structure”
that includes references to other objects
✦
Using programming terminology an object that holds references to other
objects is a container
❖
items in a container are objects
❖
the container itself is also an object
Containers (cont’d)
✦
Programs work with many different kinds of containers
list
graph
tree
2D array
Containers (cont’d)
✦
✦
✦
Containers are defined by
❖
the relationship between items in the container
❖
the operations that can be performed on the container itself
Example:
❖
in a list there is a first item
❖
each item except the last has a successor
Operations on a list include
❖
inserting a new item
❖
searching for items
❖
sorting the items
❖
counting the number of items
list
Arrays
✦
The container we’ll use in this lab is called an array
❖
these containers are actually lists
❖
they were called “arrays” in Perl, and
the name was adopted by Ruby
❖
the distinction is not important for our
projects, so we’ll just call them “arrays”
Lists grow and shrink,
items can be inserted
anywhere
Arrays have a fixed
size, some locations
can be empty
Array Objects
✦
The easiest way to make an array in Ruby: write a list of objects enclosed
in “square brackets”
>> a = [1, 1, 2, 3, 5, 8, 13, 21]
=> [1, 1, 2, 3, 5, 8, 13, 21]
✦
This statement is an assignment just like those we saw previously
❖Ruby
allocates space in its “object store”
❖creates
an object to represent the array, associates the name a with the new object
Operations on Arrays
✦
If we ask Ruby what a is, it shows us it’s an array:
>> a
=> [1, 1, 2, 3, 5, 8, 13, 21]
✦
To perform an operation on an array, write the name of the array, a period,
and the name of the operation:
>> a.length
=> 8
Array Methods
✦
The length operation and other operations are defined by methods
✦
Earlier we saw methods, like those in the Math library, that are called
simply by typing their names
>> sin(1.0)
=> 0.841470984807897
✦
Array methods behave like other methods: we call them, sometimes
passing arguments, and they return a result
>> a.length
=> 8
>> a.include?(5)
=> true
the question mark is part of
the method name
Array Methods (cont’d)
✦
Here are some examples
❖
we’ll be introducing more methods as we need them for projects
>> a = [1,1,2,3,5,8,13,21]
=> [1, 1, 2, 3, 5, 8, 13, 21]
>> a.first
=> 1
>> a.last
=> 21
>> a.reverse
=> [21, 13, 8, 5, 3, 2, 1, 1]
Array Methods (cont’d)
✦
Some methods are identified by operators
❖
one way to attach a new item to the end of an array is to use the << operator
❖
the name of this operator is two < symbols, with no space in between
>> a
=> [1, 1, 2, 3, 5, 8, 13, 21]
>> a << 34
=> [1, 1, 2, 3, 5, 8, 13, 21, 34]
>> a << 55
=> [1, 1, 2, 3, 5, 8, 13, 21, 34, 55]
Lists of Integers
✦
Since making a list with every value in a specified range is a common
operation, Ruby has a special syntax
✦
An expression of the form Array(i..j) makes a list with all values
between i and j
✦
Some examples:
>> Array(1..5)
=> [1, 2, 3, 4, 5]
>> a = Array(0..99)
=> [0, 1, 2, 3, ... 98, 99]
>> a.length
=> 100
Recap: Arrays in Ruby
✦
An array is a kind of object
❖
it’s a container, holding references to other objects
✦
A variable name can refer to an array (or a number, or a string, or any type
of object)
✦
Operations on arrays are performed by methods
❖
✦
get the first or last value, append an item to the end, search for an item, ...
Most methods are called by an expression of the form
a.operation
❖
✦
examples: a.first, a.sort, a.reverse, ...
A few methods are designated by operators
a << x
Iteration
✦
After building a container we often want to do something with each item
✦
The idea is to “step through” the container to “visit” each object
✦
This type of operation is called iteration
❖
from the Latin word iter, for “path” or “road”
To find the largest item in an
(unsorted) array an algorithm
needs to visit each item
each
✦
Ruby uses special methods called iterators to visit the items in a collection
✦
The simplest iterator is named each
✦
A typical call to each looks like this:
a.each { |x| ... x ... }
the braces (or “curly brackets”)
mark the beginning and end of
a block of Ruby code
the array to
iterate over
a variable name
written between
two vertical bar
symbols
one or more
expressions
involving x
each Example
✦
This example shows how to use each to print every item in an array
>> colors.each { |x| puts x }
red
green
since there are 3 items in colors
the body is evaluated 3 times
blue
=> ["red", "green", "blue"]
the value returned by each
✦
There are three strings in colors
✦
After placing a string in x (a new variable created for this method call) Ruby
evaluates puts x
✦
The effect of calling puts is that the value of x is displayed on the terminal
Mnemonic
✦
To remember this block notation think of how mathematicians specify the
elements in a set
✦
One way to define the set of all numbers between 1 and 10:
❖
read this as “the set of all x such that x is greater than or equal to 1 and less than or equal
to 10”
❖
the Ruby notation is similar, it just uses two vertical bars:
a.each { |x| ... x ... }
On a U.S. keyboard
the key is above the
return key
Another Example
✦
Print values to put in a table of countertop areas:
>> load "countertop.rb"
=> true
>> sides = [90, 95, 100, 105, 110, 115]
=> [90, 95, 100, 105, 110, 115]
>> sides.each { |x| puts countertop(x) }
7088
7921
8750
9673
10588
11601
Another Iterator
✦
Another method that repeats an operation is named times
❖
we won’t use it in this project
❖
introduced here just as another example of iteration
❖
use it to have Ruby evaluate expressions between the braces a fixed number of times
>> 4.times { puts "hello" }
hello
hello
hello
hello
=> 4
Recap: Iteration
✦
✦
A container is an object that holds references to other objects
❖
in Ruby an array can be used to implement a list, e.g. a list of numbers
❖
operations on containers are performed by calling methods
An iterator is a method that tells Ruby to evaluate an expression some
number of times
❖
each: evaluate the expression once for each object in a container
❖
times: evaluate the expression a specified number of times
Road Map
✦
The goal for this set of slides is to explore the Sieve of Eratosthenes
✦
Use Ruby to implement the algorithm, watch how it works
✦
What we’ve seen so far:
❖
how to test divisibility
x % p
❖
✦
how to iterate over lists
Up next: putting these ideas together
❖
we want to iterate over a list to remove composite numbers
Boolean Expressions
✦
An earlier example showed a method named include?
>> names = ["fred", "phil", "frodo"]
=> ["fred", "phil", "frodo"]
>> names.include?("phil")
=> true
>> names.include?("fannie")
=> false
✦
The true and false returned by include? are called Boolean values
✦
Expressions that create these values are Boolean expressions
A convention in Ruby: methods that return
Boolean values often have names that end
with a question mark
Comparison Operators
✦
Boolean expressions usually involve comparisons
>> x = 3
=> 3
>> x < 10
=> true
>> (5 * x) > 100
=> false
>> x == 3
=> true
>> names.length == 5
=> false
Note!
To test for equality use ==
A single = is used for assignment
Even Numbers
✦
Can you think of an expression in Ruby that will tell us if a number n is
even?
❖
hint: a number is even if the remainder of dividing by 2 is 0
❖
answer:
n % 2 == 0
✦
Some examples of how to use this expression:
>> 8 % 2
=> 0
>> 8 % 2 == 0
=> true
>> 9 % 2 == 0
=> false
Even Numbers in a List
✦
Let’s use the each iterator and the expression on the previous slide to see
which numbers in an array are even
>> a
=> [1, 1, 2, 3, 5, 8, 13, 21, 34]
>> a.each { |x| puts (x % 2 == 0) }
false
false
true
false
...
evaluates to true or false
Live Demo
A New Iterator: delete_if
✦
✦
A very useful iterator for this project is named delete_if
❖
like each, it visits each item in an array
❖
the expression in the block is expected to evaluate to true or false
❖
if the expression is true, the current item is deleted
This call to delete_if removes every even number from our list of
integers:
>> a.delete_if { |n| n % 2 == 0 }
=> [1, 1, 3, 5, 13, 21]
✦
evaluates to true or false
Note the similarities with the call to each on the previous slide:
>> a.each { |n| puts n % 2 == 0 }
prints true or false
both iterate over the entire array
both operate by placing an array element in n, one at a time
Outline
✦
✦
We now have all the pieces we need to make a list of prime numbers
❖
we’re going to replace the paper list with Ruby arrays
❖
we’ll have Ruby “cross off” multiples by using the delete_if iterator to remove them
from a list
The plan:
❖
use two arrays
❖
worksheet will hold the list of numbers to sift
❖
primes will hold the list of known primes
❖
repeat until we’re done:
• copy the first item from worksheet to primes
• remove all multiples of the most recent prime from worksheet
(see the picture on the next slide)
Outline (cont’d)
Sieve in IRB
✦
Making the two arrays is simple:
>> worksheet = Array(2..20)
Use the expressions shown earlier to
make a list of numbers from 2 to 20
=> [2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19,
20]
>> primes = []
=> []
A second array for the prime numbers
Sieve in IRB (cont’d)
✦
To copy the first item in worksheet to the end of primes:
>> primes << worksheet.first
=> [2]
✦
To delete multiples of the most recent prime:
>> worksheet.delete_if { |n| n % primes.last == 0 }
=> [3, 5, 7, 9, 11, 13, 15, 17, 19]
Almost the same expression we used
to remove even numbers
Returns true for multiples of the item at
the end of the primes list
Sieve in IRB (cont’d)
✦
To repeat the previous two steps either
❖
cut and paste the expressions in your terminal emulator window, or
❖
use command line editing to re-execute the commands
type the ↑ key twice, then return
>> primes << worksheet.first
Note these two lines are identical to the
=> [2, 3]
expressions typed before....
>> worksheet.delete_if { |n| n % primes.last == 0 }
=> [5, 7, 11, 13, 17, 19]
Live Demo
Sieve in IRB (cont’d)
✦
When you decide you don’t need to do any more filtering you will have lists
that look something like this:
>> primes
=> [2, 3, 5, 7, 11]
>> worksheet
=> [13, 17, 19]
✦
The prime numbers are spread across both lists
❖primes
has the values you know are prime -- they have passed the filter
❖worksheet
✦
has the remaining values that are “obviously” primes
You can combine them using this expression, which uses the + operator:
>> primes += worksheet
=> [2, 3, 5, 7, 11, 13, 17, 19]
A sieve Method
✦
This little “computational experiment” has given us some insight into how
the Sieve of Eratosthenes works
✦
To make an algorithm based on this copy/delete process we need to solve
two more problems
(1) How do we automate the execution of the steps?
❖
we want the computer to take control and repeat the copy and delete steps
(2) How do we know when to stop?
❖
✦
can we formalize the intuition that “obviously” no primes are left in worksheet?
Once we solve these problems we can make a method named sieve that
will generate the list for us
>> sieve(50)
Bonus: we can make lists of any size we want
=> [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47]
sieve 1.0
✦
A simple way to get Ruby to automate the steps is to simply iterate until the
working list is empty
✦
Ruby will do too much work, but it’s worth implementing this simple version
✦
❖
it’s a good demonstration for the type of Ruby statement that implements repetition
❖
it will help us “debug” the method
❖
when we are satisfied this simpler version works the way we want it to we can change it to
use a more sophisticated stopping condition
This strategy is widely used in the field
of software engineering
❖
several variations, with names such as “incremental development”, “continual testing”, and
“extreme programming”
Another Form of Iteration
✦
So far we’ve seen two forms of iteration
❖
iterating over the items in a container
❖
repeating the evaluation of an expression a fixed number of times
✦
A generalization of the second form of iteration is to repeat the evaluation
until a specified condition is reached
✦
Example: make an array with 10 random numbers
while a.length < 10
a << rand(10)
A Boolean expression (evaluates
to either true or false )
end
As long as the expression is true
Ruby evaluates the statement(s) in
the body of the while
A new keyword
A method built into Ruby
Another Form of Iteration (cont’d)
✦
This shows what happened when a while statement is used in an IRB
session:
>> a = []
=> []
>> while a.length < 10
a << rand(10)
end
The statement was split into
three lines (the way it’s
usually entered in a file)
>> a
=> [8, 7, 8, 9, 1, 1, 2, 5, 8, 5]
After the 10th number is appended
to a the call to a.length returns 10
and the expression is false
A call to rand(10) returns a random
integer between 0 and 9
while Loops
✦
Another name for this type of statement in Ruby is “while loop”
❖
✦
✦
an old name, dating to the early days of programming
You’ve probably heard the phrase “infinite loop”
❖
it’s (usually) a bug in a program
❖
it occurs when the controlling expression
never becomes false
When we write a while expression we have
to make sure something inside the loop
changes a value in the expression
❖
e.g. make sure we add something to
the array so the length eventually
reaches 10
Apple HQ is at 1 Infinite Loop,
Cupertino, CA
sieve 1.0 (cont’d)
✦
To get back to the Sieve algorithm, here is the code for the first version of
the method:
def sieve(n)
worksheet = Array(2..n)
primes = []
create two lists
while worksheet.length > 0
primes << worksheet.first
worksheet.delete_if {|x| x % primes.last == 0}
end
return primes
end
iterate until there are no more
numbers in worksheet
copy and delete steps
Tutorial Project
✦
✦
Suggested (but optional):
❖
work through the tutorial project in Section 3.6 of the text
❖
create a file named mysieve.rb
❖
cut and paste expressions from your IRB session into the file
❖
test the method as you add things to it
When you’re done:
>> load "mysieve.rb"
=> true
>> sieve(100)
=> [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59,
61, 67, 71, 73, 79, 83, 89, 97]
Terminating the Loop
✦
Let’s return to the question of how many times we need to execute the loop
❖
✦
current version: until worksheet is empty
Is there a way to formalize the intuition that well before the list is empty
there is no need to keep looking for multiples?
No multiples of 11 in worksheet
primes:
[2, 3, 5, 7, 11]worksheet:
[13, 17, 19]
Upper Bound
✦
When we call sieve we pass it n, the upper limit of the interval to search
❖
✦
e.g. sieve(1000) means we want find primes between 1 and 1000
Any number removed from worksheet must be
(i) less than n
(ii) the product of two numbers a and b
✦
A useful observation: a or b or both must be less than
❖
✦
if
and
then
That means we can stop scanning when the number at the front of
worksheet is larger than
while worksheet.first < sqrt(n)
...
end
edit the file, change the Boolean
expression that controls the
while statement
Details, Details
✦
Unfortunately this change seems to have introduced a bug:
>> load "mysieve.rb"
>> sieve(100)
=> [2, 3, 5, 7, 11]
✦
We seem to have lost most of the primes!
✦
The problem: when the loop ends, the first few prime numbers are in the
array called primes, the rest are still in worksheet
If x and y are both arrays, x + y is a new array made
by attaching y to the end of x
Change the return value to primes + worksheet
sieve 2.0
✦
Here is the final version of the method:
def sieve(n)
worksheet = Array(2..n)
primes = []
while worksheet.first < sqrt(n)
primes << worksheet.first
worksheet.delete_if { |x| x % primes.last == 0 }
end
return primes + worksheet
end
Experiments
✦
Now that we have a working version we can do some experiments that will
help us understand better how the method works
✦
The new version of the sieve method is part of a module in RubyLabs
✦
Start a new IRB session, then:
>> include SieveLab
=> Object
✦
To see the code for the sieve method:
>> Source.listing("sieve")
1:
def sieve(n)
2:
return [] if n < 2
3:
worksheet = Array(2..n)
4:
primes = []
...
Tools on the Workbench
✦
✦
Technicians use a probe to help track
down hardware problems
❖
touch the point of a metal stylus to a
pin on a CPU or memory chip
❖
the probe is connected to a monitor that
shows voltage levels or other information
The RubyLabs gem has a set of
“software probes” to help monitor
the execution of methods in lab projects
❖
measure execution time
❖
count the number of times a statement is executed
❖
print the values of variables (e.g. the contents of the worksheet array) as a program runs
Attaching a Probe
✦
To monitor the execution of a method attach a software probe
✦
First look at the listing of the method:
>> Source.listing("sieve")
...
6:
✦
while worksheet.first < sqrt(n)
7:
primes << worksheet.first
8:
worksheet.delete_if { |x| x % primes.last == 0 }
Then attach a probe to one of the lines in the method:
>> Source.probe("sieve", 7, "p worksheet")
=> true
Call trace to Monitor Execution
✦
After a probe is attached use a method named trace to monitor the
execution of the method
>> trace { sieve(50) }
[2, 3, 4, 5, 6, 7, ... 48, 49, 50]
[3, 5, 7, 9, 11, 13, ... 47, 49]
[5, 7, 11, 13, ... 47, 49]
Every time sieve reaches line 7
the probe is activated: Ruby calls
p worksheet
[7, 11, 13, ... 47, 49]
=> [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47]
Note: the probe is evaluated before line 7 is executed
Counters
✦
A special type of probe called a counter will keep track of how many times
an expression is evaluated
>> Source.probe("sieve", 7, :count)
=> true
✦
Use a method named count to count the
number of times the expression is executed
>> count { sieve(50) }
=> 4
✦
In this example the value of the counter should agree with the number of
lines printed by the call to trace
Measuring Execution Time
✦
Computers have a built-in clock
✦
A RubyLabs method named time uses the clock as a “stop-watch”
>> time { sieve(100) }
=> 0.001534
>> time { sieve(1000) }
=> 0.016214
Put any Ruby expression between braces
The result of the call to time is the number
of seconds required to evaluate the
expression
>> time { sieve(10000) }
=> 0.177472
Note: the value returned by the expression is
ignored.
Experiment
✦
✦
It may not seem like the new loop termination condition makes much of a
difference
❖
the first method stops when the worksheet is empty
❖
the second version stops when the first item in the list is greater than
The following experiment shows what sort of impact this improvement
made
❖
use time and count to measure the performance of both methods
❖
results are shown on the next slide
Results
✦
For small values of n you won’t notice much difference when you call the
two methods
✦
But when n is larger it makes a big difference
Iterations
simple
n
100 25
Time (min:sec)
sqrt
simple
n
sqrt
5
100
--
--
1,000
168
12
1,000
--
--
10,000
1229
26
10,000
0:01
--
100,000
9592
66
100,000
0:18
0:01
1,000,000
78498
169
1,000,000
20:59
0:07
Measurements made on Apple iMac with 3GHz CPU and Mac OS X 10.5
A New Tool for the Workbench
✦
Now that we have a method for making lists of prime numbers we can save
it for later use
✦
We can use it to
answer questions
about primes
❖
how many less
than n?
❖
largest gap between
successive primes
❖
prime pairs
❖
Mersenne primes
Abstraction
✦
This is a good example of abstraction
✦
We have a nice, neat package that we can save and reuse
❖
in the future we don’t have to worry about the implementation details
❖
we (and people who use it) just need to know that sieve(n) makes a list of prime
numbers between 2 and n
>> load "sieve.rb"
=> true
>> p = sieve(1000)
>> p.last
=> 997
What is the largest prime less than 1000?
>> p.length
=> 168
How many primes between 2 and 1000?
Every Method Call Returns an Object
✦
✦
One of the nice things about Ruby is that it is so consistent
❖
major complaint about Perl: too many special cases
❖
constantly need to look things up in a manual to decide if they’re possible
Every method call in Ruby returns an object
❖
the return value might be nil (“nothing”) but nil is an object
✦
A common idiom: chain of method calls
✦
Example: how many prime numbers less than 1000?
>> p = sieve(1000)=>
[2, 3, 5, ... 997]
>> p.length=> 168
>> sieve(1000).length=>
168
This works because sieve(1000) is an array object.
We can save it if we want to use it later, but it’s not mandatory
The Sieve in Practice
✦
This project on the Sieve of Eratosthenes was motivated by the importance
of prime numbers in modern cryptography
✦
Methods like RSA use huge prime numbers -- 500 or more digits
✦
These numbers are not generated by the sieve
✦
❖
there are too many prime numbers, and the worksheet would be way too long
❖
an estimate: the number of primes less than n is n / ln n
❖
for n = 10500 there are around 10497 prime numbers
But the sieve is an important “building block” in the RSA algorithm
The Sieve in Practice (cont’d)
✦
To make a huge prime number:
1. let p = sieve(1000)
2. let n be a 500-digit number chosen at random
3. if n is a multiple of any number in p go back to step 2
4. apply the “Rabin-Miller test,” a more complex and time-consuming test to see if n is prime;
if the test fails go back to step 2
✦
It seems like this method would have a hard time finding a prime number
but there are so many primes the algorithm does not need too many
iterations
❖
for 500-digit numbers nearly 1 out of every 1000 is prime
Summary
✦
The Sieve of Eratosthenes describes a process for making lists of prime
numbers
✦
For over 2000 years people used this process -- aided by paper and pencil,
abacus, or whatever technology was available
✦
In this unit we
❖
❖
❖
used IRB to manage the lists,
explore how the sieve works
created an algorithm that
controls each step in the
process
improved the algorithm after
analyzing properties of
composite numbers
Iterations
simple
n
100 25
sqrt
5
1,000
168
12
10,000
1229
26
100,000
9592
66
1,000,000
78498
169
Summary (cont’d)
✦
A final comment:
❖
computer science is more than just “programming”
❖
computer science is the study of computation
❖
computations may be performed by people or by machines
✦
A programmer is concerned with writing instructions in a programming
language in order to implement an algorithm
✦
A computer scientist is also interested in the ideas behind the algorithm
and finding ways to improve the algorithm
✦
❖
how many iterations? can we make fewer iterations?
❖
use mathematical properties of prime numbers to derive a new condition for stopping the
iteration
Good programmers are also computer scientists....