CS201 – Spring 2003
Prof.
Hartman
Homework
#8
Due Friday, April
4th by 5:00 pm
a) Create an array
with all elements initialized to 1 (1 means "might be prime"). Any number that
is prime will have a 1 in its subscripted element when the method ends. If an
element has a 0 with the method ends, then the corresponding number is a
multiple of some smaller number.
b) Starting with the
element with array subscript 2, every time you find an element that has value 1,
loop through the rest of the array, turning all multiples of the subscript to 0.
For example, there will be a 1 in the array
element with subscript 2, so we set all the later elements with subscripts that
are a multiple of 2 (subscripts 4, 6, 8, 10, etc.) to 0.
Next we see that the element with array subscript
3 has a 1 in it. So we set all the later elements with subscripts that are a
multiple of 3 (subscripts 6, 9, 12, 15, etc.) to 0.
Array element 4 is 0, so we skip it and go on to
element 5, etc.
When you have completed this process for every element
in the array, all subscripts (starting with 2) whose element contains a 1 are
prime; those that have a 0 are not prime.
Create a program that uses this algorithm to print all primes from 1 to n, where n is a number the user enters. Try the program on 100, and include this run in your sample runs.
2.
Complete
problem #2 on page 633 of your
text.