#include <stdio.h>
#include <math.h>
#include <stdlib.h>
const int max = 500000000; //checking all numbers between 2 and max*2 +1
int main() {

	char *numbers;
	numbers = (char *) malloc(sizeof(char)*max);
	
	//int primes = 1; //2 is not in the inital list, so start off with 2 as a prime
	unsigned int currentNumber = 3;
	unsigned int arrayPosition = 0;
	unsigned int maxNum = (int) sqrtf((float)max*2)/2;
	unsigned int crossOff, x;
	
	for(x = 0; x < max; x++) {
		numbers[x] = 1; //set everything to true
	}
	
	while(arrayPosition <= maxNum){
	
		if(numbers[arrayPosition]){
			crossOff = arrayPosition + currentNumber;
			//printf("crossing out multiples of %d\n", currentNumber);
			while(crossOff < max){
				numbers[crossOff] = 0;
				crossOff = crossOff + currentNumber;
			}
			//primes++;
		}
		arrayPosition++;
		currentNumber = arrayPosition*2 + 3;
	}
	
	int primes = 1; //start counting with 2
	//printf("2 is a prime\n");
	for(arrayPosition = 0; arrayPosition < max; arrayPosition++){
		if(numbers[arrayPosition]){
			//currentNumber = arrayPosition*2 + 3;
			//printf("%d is a prime\n", currentNumber);
			primes++;
		}
	}
	
	printf("Primes found: %d\n", primes);
	
	return 0;
}