primes.c


                                            #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;

                                            }