Beginning C Programming for Engineers

Homework Set 4

Problem 1 (50 points)

Again, we want to count the number of primes between 2 and 100000. But this time we will use a different algorithm, which works as follows:

Start with 2. Mark 4,6,8,10,...,100000, which are multiples of 2, as non-primes (you must find a way in C language to "mark" these numbers)
Next is 3. Mark 6,9,12,15, ..., 99999.
Then 4, 5, 6, ..., until 100000/2=50000. Those unmarked numbers must be primes (why?).

Use the unix command time to measure the execution time of your program. For example, if the executable is named prime, then the following command will show the running time.

time prime

Also, measure the execution time of the prime counting program you wrote for homework 3. Calculate the speedup (the ratio of the execution times of the two programs). These two program must be executed on the same computer.

BONUS: (20 points)

Improve the algorithm described above to make it even faster. Prove it by showing the speedup.

Problem 2 (50 points)

Write a program to compute the square of the matrix shown below (The square of matrix M is the product M*M)

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

Declare a 10 by 10 two-dimensional array to store the matrix, then populate the array with proper values using a nested loop. Do NOT use initializers to initialize the array. To make sure that you get the correct matrix, print it out before the computation.