/*
 * Sieve of Erasthones:
 * Print the prime numbers from 0 through 999 
 *

#include <stdio.h>
#include <math.h>

#define N	1000

int main () {
	int	i, j, s;
	int	is_prime[N];	/* if is_prime[i] == 0, then i isn't prime */

	/* initially, all are presumed prime */

	for (i=0; i<N; i++) is_prime[i] = 1;	

	/* find the limit of the numbers to count up to */

	s = (int) sqrt (N) + 1;

	/* for each i in 2..sqrt(N), mark out multiples of i */

	for (i=2; i<s; i++) {

		/* mark out 2i, 3i, 4i, ... */

		for (j=2*i; j<N; j+=i) is_prime[j] = 0;
	}

	/* print out the numbers that are left */

	for (i=2; i<1000; i++)
		if (is_prime[i]) printf ("%d\n", i);
}