/* $Id: Sieve.c $ */

/* Sieve of Eratosthenes algorithm 
 * Ref: http://www.math.utah.edu/~alfeld/Eratosthenes.html
 * This implementation by David Ireland <www.di-mgt.com.au>
 * $Date: 2012/12/14 11:02Z $
 * $Author: dai $
 */

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


/* Usage: Sieve n
 * where n = largest integer to test for prime
 * (default = 1000)
 */

/* For first 10,000 primes use 
      Sieve 104729
   because 104729 is the 10,000th prime
   Ref: http://www.utm.edu/research/primes
*/

main(int argc, char *argv[])
{
	int i, m, k;
	int klimit, nlimit;
	int *mark;

	if (argc > 1)
		nlimit = atoi(argv[1]);
	else
		nlimit = 1000;

	mark = calloc(nlimit, sizeof(int));

	/* Calculate limit for k */
	klimit = (int)sqrt((double)nlimit) + 1;

	/* Mark the composites */
	/* Special case */
	mark[1] = -1;

	/* Set k=1. Loop until k >= sqrt(n) */
	for (k = 1; k <= klimit; k = m)
	{
		/* Find first non-composite in list > k */
		for (m = k + 1; m < nlimit; m++)
			if (!mark[m])
				break;

		/* Mark the numbers 2m, 3m, 4m, ... */
		for (i = m * 2; i < nlimit; i += m)
			mark[i] = -1;
	}

	/* Now display results - all unmarked numbers are prime */
	for (k = 0, i = 1; i < nlimit; i++)
	{
		if (!mark[i])
		{
			if (k % 10 == 0)
				printf("%d: ", k);
			printf("%d ", i);
			k++;
			if (k % 10 == 0 && k > 0)
				printf("\n");
		}
	}
	printf("\n");

	free(mark);

	return 0;
}