/********************************************
 * Prime Number Calculator
 * (C) 2006 Kevin Mehall
 * BSD License (See bottom of file)
 * 
 * Read the associated tutorial at http://bluemonkey.us/blog/finding-prime-numbers-2
 *
 * This program uses the Sieve of Eratosthenes.
 *
 * compile with : gcc -O3 -lm primes.c -o primes
 *
 *********************************************/

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

#define TO 20000000  /* edit this line to change where the search ends */
#define DEBUG 0 /* If set to 1, display debugging info as we go */
#define WRITE 0 /* If set to 1, print a list of the prime numbers. Set to 0 for timing*/

#define COMPOSITE 1
#define UNKNOWN 0

int main(){
	int i=2;
	int endpt;
	char *a=malloc(TO); /* Not memory efficient: wastes space by a factor of 8, but much simpler. This could be an array of bits*/
	
	endpt=(int)(sqrt(TO)+0.5);/* Square root of length */
	
	memset(a, 0, TO); /* set all items to 0 (unknown) */
	
	while (i<endpt) {
		int x=i*2; /* First multiple of i */
		while (x<TO){/* mark all multiples of i as composite */
			a[x]=COMPOSITE;
			#if DEBUG
			fprintf(stderr, "Marking %i as composite (factor %i)\n", x, i);
			#endif
			x+=i; /* Go to next multiple */
		}
		i++; /* Otherwise, we just find the current one again */
	
		while (a[i]==COMPOSITE && i<endpt) { /* skip composites */
			i++;
		}/* i is now next number not currently considered composite */
	}
	
	#if WRITE
	for (i=2; i<TO; i++){ /* print all  numbers that are  not composite*/
		if (a[i]!=COMPOSITE){
			printf("%i\n", i);
		}
	}
	#endif
	free(a);
	return 0;
}

/*
* Copyright (c) 2006, Kevin Mehall
* All rights reserved.
*
* Redistribution and use in source and binary forms, with or without
* modification, are permitted provided that the following conditions are met:
*     * Redistributions of source code must retain the above copyright
*       notice, this list of conditions and the following disclaimer.
*     * Redistributions in binary form must reproduce the above copyright
*       notice, this list of conditions and the following disclaimer in the
*       documentation and/or other materials provided with the distribution.
*     * Neither the name of the <organization> nor the
*       names of its contributors may be used to endorse or promote products
*       derived from this software without specific prior written permission.
*
* THIS SOFTWARE IS PROVIDED BY Kevin Mehall ``AS IS'' AND ANY
* EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
* WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
* DISCLAIMED. IN NO EVENT SHALL <copyright holder> BE LIABLE FOR ANY
* DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
* (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
* LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
* ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
* (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
* SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.

*/