Homework 8

The Sieve of Eratosthenes
A prime integer is any integer that can be divided evenly only by itself and 1. The Sieve of Eratosthenes is a method of finding prime numbers. It works as follows:
  1. Create an array with all elements initialized to 1 (true). Array elements with prime subscripts will remain 1. All other array elements will eventually be set to zero.
  2. Starting with array subscript 2 (subscript 0 is not used and subscript 1 is prime by definition), every time an array element - of subsript i, say - is found whose value is 1, loop through the remainder of the array and set to zero every element whose subscript is a multiple of i. For example, for array subscript 2, all elements beyond 2 in the array that are multiples of 2 will be set to zero (subscripts 4, 6, 8, 10, etc.). For array subscript 3, all elements beyond 3 in the array that are multiples of 3 will be set to zero (subscripts 6,9, 12, 15, etc.).
When this process is complete, the array elements that are still one indicate that the subscript is a prime number. These subscripts can then be printed. Write a program that uses an array of 1000 elements to determine and print the prime numbers between 1 and 999. Ignore element 0 of the array.

Additional hints can be found here

Remember:
It is due Mo 3/29, late homeworks will be penalized !
Turn in a print-out of your code and a scriptfile.
You will be graded on:

  1. correctness: (6 points)
  2. style: (4 points)