0 0

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 ints, 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.). Arrays elements with subscripts 0 and 1 are to be ignored, as we will start with 2 as the first number to consider for primeness.

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 already 0, do not go thru the process, and just move on to the next element.

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' subscripts are precisely the prime numbers you are seeking.

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 2, and change all those elements to 0. This is what you get, because 4, 6, 8, and 10 are multiples of 2:

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 skip that element altogether. It is important to understand why it's OK to skip it.

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