Crivo de Eratóstenes (números primos)

/* O Crivo de Eratóstenes (Sieve Eratosthenes) é um algoritmo e um método simples e prático para encontrar números primos até um certo valor limite. Segundo a tradição, foi criado pelo matemático grego Eratóstenes (c. 285-194 a.C.), o terceiro bibliotecário-chefe da Biblioteca de Alexandria. */

// Apple Xcode
// Sieve Eratosthenes


#include <stdio.h>

#define N 1000


int main (int argc, const char * argv[]) {

    // Sieve Eratosthenes: 100 primeiros
    int i, j, a[N + 1];

    for (a[1] = 0, i = 2; i <= N; i++) {
        a[i] = 1;
    }

    for (i = 2; i <= N/2; i++) {
        for (j = 2; j <= N/i; j++) {
            a[i * j] = 0;
        }
    }

    for (i = 1; i <= N; i++) {
        if (a[i]) {
            printf("%4d", i);
        }
    }

    printf("\n");


    return 0;
}