#include <stdio.h>
#include <stdlib.h>

#define MAX 10000000
#define CACHE_MAX 1000

/* Compute the sqrt(n) using Newton's approximation method.
** It is only accurate for n >= 5 because it relies solely
** on integer arithmetic */
int msqrt(int n)
{
	int prev, cur = n, diff;

	do
	{
		prev = cur;
		cur = (prev + n/prev)/2;

		diff = prev - cur;
		if(diff < 0) diff = -diff;
	} while(diff > 1);
	return cur;
}

/* Check if n is prime, first using cache as a source of possible divisors.
** Cache is an ordered table of primes.  If we reach the end without exceeding
** sqrt(n), we manually try remaining possible divisors <= sqrt(n) */
int isprime(int n, int cache[], int *end)
{
	int max = msqrt(n), tmp = 1;
	while(cache < end)
	{
		tmp = *cache;
		if(tmp > max) return 1;
		if(n % tmp == 0) return 0;
        cache++;
	}
	for(tmp += 2; tmp <= max; tmp += 2)
	{
        if(n % tmp == 0) return 0;
	}
	return 1;
}

/* Iterate from 2 to max, checking if i is a prime, and keeping track
** of the number of primes we find.  The first CACHE_MAX primes we find
** are saved in cache. */
int checkprimes(int max, int cache[], int *len)
{
	int i = 1, count = 1, *pos = cache, *end = cache + CACHE_MAX;

	*pos = 2;
    pos++;

	for(i += 2; i < max; i+=2)
	{
		if(isprime(i, cache, pos))
		{
			if(pos<end)
			{
				*pos = i;
				pos++;
			}
			count++;
		}
	}
	*len = pos - cache;
	return count;
}

/* Find and display the number of primes less than MAX */
int main(int argc, char *argv[])
{
	int size, cache[CACHE_MAX], max = MAX;
	int count = checkprimes(max, cache, &size);
	printf("%d\n", count);
	return 0;
}