#include <stdio.h>
#include <math.h>
#include <assert.h>
#include <time.h>
 
int main(){
        int i;
        printf("Find primes up to: ");
        scanf("%i",&i);
 
        clock_t start, stop;
        double t = 0.0;
       
        assert((start = clock())!=-1);
       
        //create prime list
        int prime[i];
        int c1, c2, c3;
       
        //fill list with 0 - prime
        for(c1 = 2; c1 <= i; c1++){
                prime[c1] = 0;
        }
       
        //set 0 and 1 as not prime
        prime[0]=1;
        prime[1]=1;
       
        //find primes then eliminate their multiples (0 = prime, 1 = composite)
        for(c2 = 2;c2 <= (int)sqrt(i)+1;c2++){
                if(prime[c2] == 0){
                        c1=c2;
                        for(c3 = 2*c1;c3 <= i+1; c3 = c3+c1){
                                prime[c3] = 1;
                        }
                }
        }
       
        stop = clock();
        t = (double) (stop-start)/CLOCKS_PER_SEC;
       
        //print primes
        for(c1 = 0; c1 < i+1; c1++){
                if(prime[c1] == 0) printf("%i\n",c1);
        }
        printf("Run time: %f\n", t); //print time to find primes
       
return 0;
}