Programing assignment: C Prime Number

In this program you will write a C program to find all prime numbers less than 10,000. You should use 10,000 bits to correspond to the 10,000 integers under test. You should initially turn all bits on (off) and when a number is found that is not prime, you should turn the corresponding bit off (on). Completion of the program requires going through all bits and printing the decimal numbers corresponding to those bits that remain on (off).

You should use the Sieve of Eratosthenes algorithm to find all the primes. The algorithm will be discussed in class. You should investigate some efficiency steps to improve the performance of the algorithm to be measured in the number of comparisons and byte assignments that you use. For example, consider how you might make use of the fact that all even numbers after 2 will not be prime or how to reduce the number of comparisons and assignments when marking off multiples of higher primes.

After finding all primes, you should print the prime numbers out as decimal (base 10) numbers.

There may be a large number of prime numbers less than 10,000. To minimize the output, you should print the first 500 primes so that there are 5-10 prime numbers per line. You should then print a summary line of the total number of prime numbers that you found less than 10,000.

To provide a sense of how efficient your program is, you should output a count of the number of comparisons and the number of assignments that your program has performed. This will be discussed further in class.

Be sure to submit an analysis of the results of your program. The analysis should include the number of comparisons and the number of assignments as a summary of the output from your program and some verification that the results are correct.

The program should be written to be as efficient as possible.

You should call printf with a decimal format (%d) to print a number. If you use a format of the form %7d as an example, it will print the number in a field width of 7. That is very convenient for printing the numbers in columns.