#include <stdio.h>
#include <math.h>
#define LIMIT	3000000

/* Sieve of Erasthones, returning number of primes from 2 through n 
 * (this function is often called 'pi' in number theory for no
 * clear reason :-)
 */
int pi (int n) {
	int	i, j, lim, count;
	char 	S[LIMIT+1]; /* used as truth values */

	/* first, mark all the even numbers as not prime,
	 * and all the odd numbers as tenatively prime
	 */
	for (i=2; i<=n; i+=2) {
		S[i] = 0;
		S[i+1] = 1;
	}

	/* but 2 is a prime */

	S[2] = 1;

	/* 'lim' is the largest increment we will use in the sieve */

	lim = (int) sqrt (n) + 1;

	/* start from three and go up to sqrt (n) */

	for (i=3; i<=lim; ) {

		/* mark out all multiples of i */

		for (j=i+i; j<=n; j+=i) S[j] = 0;

		/* find the next non-marked-out number to use
		 * as the next increment
		 */

		for (i+=2; !S[i]; i+=2);
	}

	/* count them all up and return */

	count = 0;
	for (i=2; i<=n; i++) count += S[i];
	return count;
}

int main (int argc, char *argv[]) {
	int	i, count, n;

	
	/* get n from argv */

	if (argc != 2) {
		fprintf (stderr, "Usage: %s <number-of-primes>\n", argv[0]);
		exit (1);
	}
	n = atoi (argv[1]);
	if (n > LIMIT) {
		fprintf (stderr, "number is too large!\n");
		exit (1);
	}

	/* call the sieve and print the results */

	printf ("F(%d) = %d\n", n, pi (n));
	return 0;
}