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