prime-search.c

/* ACSEF Program: find prime numbers */
/* Compile with -DDEBUG to print all primes */

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

#define MAX_PRIME 100000000

int main(int argc, char **argv) {

    clock_t start = clock();

    /* This program uses Eratosthenes' sieve */
    /* allocate sieve */
    bool *sieve = malloc(MAX_PRIME * sizeof(bool));
    
    /* initialize sieve with numbers */
    for(int i = 0; i < MAX_PRIME; i++) {
        sieve[i] = true;
    }

    /* find primes */
    int smallest_prime = 2;
    while(smallest_prime < MAX_PRIME) {

        #ifdef DEBUG
            printf("%i\n", smallest_prime);
        #endif

        /* mark all multiples of current prime by setting value to -1 */
        for(int i = smallest_prime; i < MAX_PRIME; i += smallest_prime) {
            sieve[i] = false;
        }
    
        // find smallest unmarked number
        bool should_continue = false;
        for(int i = smallest_prime + 1; i < MAX_PRIME; i++) {
            if(sieve[i]) {
                smallest_prime = i;
                should_continue = true;
                break;
            }
        }

        if(!should_continue) {
            break;
        }

    }

    double time = (double)(clock() - start) / CLOCKS_PER_SEC;
    printf("%i %f", smallest_prime, time);

    return 0;

}