/* Arquivo: crivo.c
 * ----------------
 * Este programa determina todos os primos menores que n, para um dado n.
 * Para isso, usa o metodo conhecido como o Crivo de Eratostenes.
 *
 * O programa faz uso de um vetor a[2..n-1] que e' inicializado com 1.
 * (Note que os indices 2..n-1 sao exatamente os numeros que desejamos 
 *  descobrir se sao primos ou nao.)
 * 
 * No final, as entradas desse vetor serao 0 ou 1, sendo que 
 *   a[i] = 1 indica que i e' primo e
 *   a[i] = 0 indica que i nao e' primo. 
 */

#include <stdio.h>
#define NMAX 10000
int main()
{
    int i, j, n, a[NMAX];

    printf("De o valor de n (menor que 10000): ");
    scanf("%d", &n);

    for (i = 2; i < n; i++)
	a[i] = 1;

    for (i = 2; i < n; i++)
	if (a[i])
	    for (j = i; i * j < n; j++)
		a[i * j] = 0;

    for (i = 2; i < n; i++)
	if (a[i])
	    printf("%4d ", i);
    printf("\n");
    return 0;
}

/*
 * Você entendeu por que j começa em i? E por que zeramos as posicoes i*j?
 * 
 * O que acontece se o teste "if (a[i])" for retirado? 
 * 
 */