Lab 10: (Arrays) .. and Iterators
Update your repository
As always, start by running the following command in your repository to pull the most recent changes:
git pull
Logistics
All files referenced in this lab will be found in the lab10 subdirectory of your repository.
Prime Numbers and the Sieve of Eratosthenes
Prime numbers are of great interest to mathematicians and computer scientists alike -- among other things, prime numbers are extensively used in cryptography and encryption.
Finding prime numbers (and determining if a given number is prime) is, consequently, a subject of intense research. While generating large (consisting of thousands of digits) primes is difficult and not completely understood, finding smaller prime numbers can be done fairly efficiently with an ancient method known as the Sieve of Eratosthenes.
Given that we have a list of numbers from 2 (the smallest prime) up to N, the Sieve of Eratosthenes works as follows:
- Starting with the number 2, cross off all multiples of 2 (2, 4, 6, 8, ...) all the way up to N.
- We then select the next number remaining on the list greater than 2 (which would be 3), and cross off all multiples of that number up to N.
- Repeat this procedure for each number k remaining on the list -- moving up and ignoring numbers as they are crossed off -- until (k × k) is greater than N.
For the list of numbers 2 through 25, the following sequence demonstrates the method being applied:
Start with:
2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25
After removing multiples of 2:
2 3 5 7 9 11 13 15 17 19 21 23 25
After removing multiples of 3:
2 3 5 7 11 13 17 19 23 25
After removing multiples of 5:
2 3 5 7 11 13 17 19 23
7 × 7 > 25 (the original limit), so we're done! All numbers on the list are prime.
Exercise 1: Implementing the Sieve
For your first exercise you'll implement the Sieve of Eratosthenes using an array.
Your program will prompt the user for an integer upper bound, and your program will proceed to print out a listing of all prime numbers up to the specified bound.
A few hints:
- "Crossing out" values from an array can be viewed as setting the corresponding position to
nil - Initially creating an array of numbers from 2 through limit (assuming the latter is a variable that refers to an integer) can be done with the expression
(2..limit).to_a-- the(2..limit)expression is a range in Ruby (we haven't talked about them), and theto_amethod converts that range into an array - After you've got yourself an array of numbers separated by
nils, you can use the arraycompactmethod to obtain a new array with the interveningnils removed. E.g.,[1, nil, 2, nil, 3, nil, nil, 4].compact→[1, 2, 3, 4]
Save your program as "lab10ex1.rb" -- your implementation will be evaluated for correct output and adherence to the procedure outlined above.
Exercise 2: Iterator Puzzles
For this exercise, you'll have the chance to try your hand at writing a number of "one-liner" solutions to problems involving arrays. Each of your solutions should make use of an iterator invocation (one of collect, select, reject, or inject), operate on the given array, and produce the given output.
For this exercise you'll need to be sure you pulled the most recent repository changes, as the "lab10ex2.rb" file contains the puzzles you'll be solving for this exercise. After opening the file, you'll find 12 variables that are assigned the hardcoded "solution" to each puzzle. Delete and substitute each solution with your code -- note that a "one-liner" solution isn't a requirement, but a challenge!