CS 2073 Section 2, Spring 2009
Assignment 5: Functions: countprimes.c

We have seen many examples of functions in class and in the book. One function that is often used is:

F(n) = the number of prime integers from 2 through n.

This function has the positive integers for both its domain and range. It simply counts the number of prime numbers between 2 and some other integer. For example, F(10) is 4, since there are four primes from 2 through 10, i.e., 2, 3, 5 and 7. Here are some of the values of F: 

 n		F(n)
---		----
10		4
20		8
30		10
100		25
200		46
500		95
1,000		168
1,000,000	78498
3,000,000	216816
Write a program called countprimes.c that accepts an integer command line argument, then computes F on this integer. So if the user types 
./countprimes 1000
the output should be 
F(1000) = 168
Your program should work for values up to 1,000,000,000. Your program should have a function called numprimes that computes F above. Call this function from main to get the answer. Your main function could look like this: 
int main (int argc, char *argv[]) {
	int	n;

	/* if number of arguments not 2, give an error and exit */

	if (argc != 2) {
		fprintf (stderr, "Usage: countprimes \n");
		exit (1);
	}

	/* find out n */

	n = atoi (argv[1]);

	/* print the number of primes */

	printf ("F(%d) = %d\n", n, numprimes (n));
	exit (0);
}
You must write a function called numprimes that computes F; points will be taken off if you do everything in main, even if it works. You are not limited to just main and numprimes, though; you may write other functions as well. For instance, it may help to write a function called is_prime that returns true if and only if its integer parameter is prime.

Remember, you are only going to compute F for one value, that is the value the user specifies on the command line. Don't read anything in with scanf. Don't let numprimes do any printing; leave that to main. Your program should only print something like e.g. 

F(1000) = 168
without any fancy headers, beeps, etc. The professor's executable version of countprimes is available in ~dj/bin/countprimes; you can use it to check your output.

Extra Credit

There are several ways to write this program, some faster than others. The student with the fastest program in the class will be awarded five extra points. The next three fastest programs will be awarded three extra points. No extra credit will be awarded to programs that produce incorrect output (e.g., int main () { printf ("1\n"); } is pretty fast, but it's also wrong). The programs will be timed on several large integers, and the programs with the fastest average times will be given the extra points. The time program will be used for the timings; you can do this yourself with e.g.: 
time ./countprimes 1000000
The output will look something like: 
F(1000000) = 78498
0.472u 0.004s 0:00.47 100.0%    0+0k 0+0io 1pf+0w
The first field, with u after a number, has the number of seconds spent in your code; this is the time that will be used to calculate the extra points (in this case the program took 0.472 seconds). An extra 3 points will be awarded to any program that is faster than the professor's program. Try out the program ~dj/bin/countprimes2; it's an even faster version that your professor helped develop in collaboration with others. Beat this one and we'll see what extra you get.

To turn in the program, e-mail the source code to the teaching assistant with the subject "CS2073 Assignment 5".

As always, the code you write should be your own. Don't collaborate with your classmates and don't use code you obtained somewhere else. You won't get any extra points for turning in someone else's code.

This program is due Tuesday, April 7, 2009