/*
 * File: sieve.c
 * Author: Henrik Bjoerklund
 * Date: 23. Oct. 2009
 * Description: An implementation of the sieve of Eratosthenes
 * Usage: sieve <number>
 *        where <number> is the natural number up to which we want
 *        to find the primes. The program runs the sieve and prints
 *        the primes up to <number> on stdout.
 */

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

/* Function: initArray
 * Description: Takes an array and its length and fills it
 *  with the numbers from 1 to length)
 */

void initArray(int * array, int length){
	int i;
	for(i = 0 ; i < length ; i++){
		array[i] = i+1;
	}
}

/* Function: printPrimes
 * Description: Takes an int-array and its length and prints
 *     all nonzero elements on stdout.
 */

void printPrimes(int * array, int length){
	int i;
	for( i = 0 ; i < length ; i++){
		if(array[i] != 0) printf("%d ", array[i]);
	}
	printf("\n");
}

/* Function: sieve
 * Description: Takes an int-array and its length and
 *    performes the sieve of Eratosthenes. The array
 *    is assumed to contain the numbers from 1 to length.
 *    All non-prime elements are set to 0.
 */

void sieve(int * array, int length){
	int i,j;
	array[0] = 0;     /* 1 is not considered a prime */

	/* Let i go from 2 to length and perge all multiples
	 *    of i (other than i*1) from the array.
	 */	
	for(i = 2 ; i < length ; i++){
		for(j = i*2 ; j <= length ; j += i){
			array[j-1] = 0;
		}	
	}
}

/* Function: main
 * Description: reads an positive integer n from the command line
 *     input. Creates an array of length n, fills it with the 
 *     numbers 1 to n, performes the sieve of Eratosthenes, and
 *     prints all the primes between 1 and n to stdout.
 */

int main(int argc, char ** argv){
	int n;
	int * array;
	/* Check that there is a positive integer as first
 	 * command line argument.
	 */
	if(argc <= 1 || sscanf(argv[1],"%d", &n) != 1){
		printf("Usage: sieve <number>\n");
		return 0;
	}
	/* allocate memory for the array */
	array = (int *) calloc(n,sizeof(int));

	/* initialize */
	initArray(array, n);
	/* perform the sieve */
	sieve(array, n);
	/* print the primes */
	printPrimes(array,n);
	/* deallocate memory */
	free(array);
	return 0;
}