V22.0380-001, Fall 2001, Evan Korth

Homework #5

Sieve of Erasthones (Prime
Numbers)

**Due**: Tuesday, August 6

**No
Late submissions will be accepted for this homework!**

**This
writeup is long and detailed. Take some time to read it carefully! Then, you
will see that writing this program is not very hard at all. The key is
reading the writeup carefully!**

** **

**As
you read this writeup, be sure to keep in mind the crucial distinction between
"subscript" and "element".**

** **

**Goal**: The purpose of this assignment is to give you
some practice with arrays; hopefully you will find it interesting, too.

** **

**NOTE:
You must use the method for finding prime numbers described here in this
writeup, or you will receive 0 for this homework!**

** **

**What you need to do**: You are to are to declare an
array of *int*s, in such a way as to find and output to the screen all
prime numbers between 2 and 1000 (inclusive). The method you will use is called
the ** Sieve of Erasthones** (whoever he was).

**Here's how to do it**: Declare an *int* array,
named anything reasonable, of your choice. You want 1000 as the **last
subscript** in your array (but remember: **you must** **use a symbolic
constant, **created with ** #define**, as discussed in class, and in
your reading.).

**CRUCIAL: Initialize all elements of the array to 1**.
Elements with subscripts 0 and 1 don't really matter.

**Now, perform the following process on the element with
subscript 2**: Scan through the entire array, starting with the very next
element (the element with subscript 3), and every time you find an element
whose **subscript** is a *multiple of 2*, set that element to 0. This
will result in those elements with subscripts 4, 6, 8, ..., being set to 0.

**Now, perform the exact same process on the element with
subscript 3**, starting your scan on the very next element (the one with
subscript 4). Every time you find an element with a **subscript **which is a
multiple of 3 (6, 9, 12, ...) set that element** **to 0. If you find an element
which is **already** 0, just leave it alone.

**Next, you would expect to perform the exact same
process on the element with subscript 4**, starting your scan on the very
next element (the one with subscript 5). However, since that element (the one
with subscript 4) is

**If that element is 1, perform the process. If it is
already 0, skip the process**. It is important that you figure out why you
should skip this process when the element you are considering is already 0.

Now, repeat this process over and over. When you have
finished, you will find that the array elements with **value** still ** 1**,
those elements'

Here is a "visual" example, but check out the
important note on **efficiency** below.

*Suppose you want to find all prime numbers between 2 and
10*, inclusive (your actual homework program will really look from 2 to *1000*).
Your array might look like this when you start (*after you've initialized all
elements to 1*):

subscript 0
1 2 3 4 5
6 7 8 9 10

--
-- -- -- -- --
-- -- -- -- --

element 1
1 1 1 1 1
1 1 1 1 1

**Start by looking at the element with subscript 2 **(as
described above). Find all ** subscripts **(starting with 3) which are
multiples of

subscript 0
1 2 3 **4** 5 **6** 7 **8** 9 **10**

--
-- -- -- -- --
-- -- -- -- --

element 1
1 1 1 **0** 1 **0** 1 **0** 1 **0**

**Now move on to the element with subscript 3**. Repeat
the process. That is, find all subscripts (starting with 4) which are multiples
of **3**, and change all those elements to 0 (if you find an element which
is already 0, it's OK to "change" it to 0. It just stays 0, which is
fine). This is what you get, because 6 and 9 are multiples of 3:

** **

subscript 0
1 2 3 4 5 **6** 7
8 **9** 10

--
-- -- -- -- --
-- -- -- -- --

element 1
1 1 1 0 1 **0** 1
0 **0** 0

Now move on to the element with subscript 4. That element is
** already 0**, so just

** **

Now move on to the element with subscript 5. *That element
is still 1*, so perform the process. That is, find all subscripts (starting
with 6) which are multiples of 5, and change all those elements to 0 (if you
find an element which is already 0, it's OK to "change" it to 0. It
just stays 0, which is fine). This is what you get (*nothing changed, because
the element with subscript 10 was already 0*)

** **

subscript 0
1 2 3 4 5
6 7 8 9 10

--
-- -- -- -- --
-- -- -- -- --

element 1
1 1 1 0 1
0 1 0 0 0

** **

If you think about
it, you'll see that **you don't need to perform this process past subscript 5**
(in ** this** example, not in your actual homework with the much
larger arrary). Again, it is important that you understand why.

Looking at the final array just above, note which elements
(starting with subscript 2), still contain the value 1. You come up with
subscripts 2, 3, 5, and 7. **These are precisely the prime numbers you are looking for.**

** **

**NOTE**: **Efficiency **is important here, points will
be deducted for glaring examples of inefficiency: **hint**: You do
not need to perform the process described above on **all** elements of the
array, for two different reasons: **one**: if an array element has *already
been set to 0*, what does this tell you about the multiples of that
element's subscript? **two**: 800, for example, cannot have any multiples
less than or equal to 1000. **Generalize this idea to make your program much
more efficient**.

**Another hint on efficiency**: Let's say, for argument's
sake, your array name is *primes*. Let's say you are considering the
element with subscript **3**, and you want to assign 0 to primes[**6**],
primes[**9**], primes[**12**], primes[**15**], etc. You might be
tempted to look at primes[**4**], primes[**5**], primes[**6**],
primes[**7**], primes[**8**], primes[**9**], etc, and see which
subscripts are multiples of three. ** Do you see how this can be done more
efficiently**?

**Some requirements**:

**Use of functions**: We did not learn in class about how
to pass arrays as arguments to functions (we will do so on Monday). Therefore, in this particular
program, your best bet is just write *main()*, and *do not write any
additional user-defined functions*.

You must use a **#define** (symbolic constant) for the
size of the array, and **you must use this constant as appropriate throughout
your entire program**.

**Important requirement**: Your program should be written
so that if you want your program to find the prime numbers from 2 up to 5000
instead of up to 1000, the ***only* thing you need to change is the #define**!

**Note**: You must find a way to **prevent the output
from scrolling so fast that the user cannot see the output**. In other words,
find a way to make the scrolling output pause every 20 lines or so of output,
and **prompt the user to press <enter> to see the next screenful of
output**. **Hint**: the **mod** (%) operator may be useful here.

** **

**Sample
Output: (every time you see "Press <enter> to see more output",
the program pauses so the user can view the screenful of info, waits for the
user to hit <enter>, then shows the next screenful).**

** **

2 is prime

3 is prime

5 is prime

7 is prime

11 is prime

13 is prime

17 is prime

19 is prime

23 is prime

29 is prime

31 is prime

37 is prime

41 is prime

43 is prime

47 is prime

53 is prime

59 is prime

61 is prime

67 is prime

71 is prime

Press
<enter> to see more output...

73 is prime

79 is prime

83 is prime

89 is prime

97 is prime

101
is prime

103 is prime

107 is prime

109 is prime

113 is prime

127 is prime

131 is prime

137 is prime

139 is prime

149 is prime

151 is prime

157 is prime

163 is prime

167 is prime

173 is prime

Press
<enter> to see more output...

179 is prime

181 is prime

191 is prime

193 is prime

197 is prime

199 is prime

211 is prime

223 is prime

227 is prime

229 is prime

233 is prime

239 is prime

241 is prime

251 is prime

257 is prime

263 is prime

269 is prime

271 is prime

277 is prime

281 is prime

Press
<enter> to see more output...

283 is prime

293 is prime

307 is prime

311 is prime

313 is prime

317 is prime

331 is prime

337 is prime

347 is prime

349 is prime

353 is prime

359 is prime

367 is prime

373 is prime

379 is prime

383 is prime

389 is prime

397 is prime

401 is prime

409 is prime

Press
<enter> to see more output...

419 is prime

421 is prime

431 is prime

433 is prime

439 is prime

443 is prime

449 is prime

457 is prime

461 is prime

463 is prime

467 is prime

479 is prime

487 is prime

491 is prime

499 is prime

503 is prime

509 is prime

521 is prime

523 is prime

541 is prime

Press
<enter> to see more output...

547 is prime

557 is prime

563 is prime

569 is prime

571 is prime

577 is prime

587 is prime

593 is prime

599 is prime

601 is prime

607 is prime

613 is prime

617 is prime

619 is prime

631 is prime

641 is prime

643 is prime

647 is prime

653 is prime

659 is prime

Press
<enter> to see more output...

661 is prime

673 is prime

677 is prime

683 is prime

691 is prime

701 is prime

709 is prime

719 is prime

727 is prime

733 is prime

739 is prime

743 is prime

751 is prime

757 is prime

761 is prime

769 is prime

773 is prime

787 is prime

797 is prime

809 is prime

Press
<enter> to see more output...

811 is prime

821 is prime

823 is prime

827 is prime

829 is prime

839 is prime

853 is prime

857 is prime

859 is prime

863 is prime

877 is prime

881 is prime

883 is prime

887 is prime

907 is prime

911 is prime

919 is prime

929 is prime

937 is prime

941 is prime

Press
<enter> to see more output...

947 is prime

953 is prime

967 is prime

971 is prime

977 is prime

983 is prime

991 is prime

997 is prime

Hit
<enter> to terminate program...

**Good
luck
**