CS 1713 Section 2, Fall 1997
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 (also confusingly called the "pi" 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 3,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 number of primes */

	n = atoi (argv[1]);

	/* too many?  give an error and exit */

	if (n > 3000000) {
		fprintf (stderr, "Number too big!\n");
		exit (1);
	}

	/* print the number of primes */

	printf ("F(%d) = %d\n", n, countprimes (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(100) = 168
without any fancy headers, beeps, etc. The instructor's executable version of countprimes is available in ~djimenez/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 /usr/bin/time program will be used for the timings; you can do this yourself with e.g.: 
/usr/bin/time countprimes 1000000
The output will look something like: 
F(1000000) = 78498
 
real        1.1
user        0.8
sys         0.2
The user field it the amount of time spent in your programs code; this is the time that will be used to calculate the extra points (in this case the program took 0.8 seconds). (Don't use the time command on Unix; it is different from /usr/bin/time.) An extra 3 points will be awarded to any program that is faster than the instructor's program.

To turn in the program, e-mail the source code to the instructor and, as always, remember to post your progress report to the newsgroup when the program is due.

This program is due Wednesday, October 29, 1997.