Gerador de Primos

Codigo C de um gerador de primos até 2 milhões, baseado no Crivo de Eratóstenes. Constrói um array de primos e imprime-o para o stdout. Demora menos de meio segundo a ser computado (excluindo os printfs).

#include<stdio.h>
#include<stdlib.h>
#include<math.h>
#define N 2000001

/**
 * Algoritmo baseado no Crivo de Eratostenes
 * Dado um array de 0..N-1 retorna o array com todos os primos até N-1
 * Coloca 0 nos nao-primos e depois retira-os do array
 */
int
sieve (int arr[], int pos, float sqrtm)
{
  int i = 0, z = 0, salto = 0, inicio = 0;
  z = pos;
//C.P - O algoritmo para quando o numero que queremos verificar e' maior
//que a raiz de N
  if (arr[pos] > sqrtm)
    return 0;
//avanca ate' encontrar o proximo numero diferente de 0
  while (arr[z] == 0)
    z++;
//define o salto e inicio   
  salto = arr[z];
  inicio = arr[z] + arr[z];
//muda os multiplos do numero que saltou para 0
  for (i = inicio; i < N; i = i + salto)
    arr[i] = 0;
  return sieve (arr, pos + 1, sqrtm);
}

/*
 * Preenche o array com 0 1 2 3 4 ... N-1
 */
void
initArray (int arr[])
{
  int i;
  for (i = 0; i < N; i++) {
    arr[i] = i;
  }
}

/*
 * Retira os zeros do array de primos
 */
int
retiraDesnecessariosArrayPrimos (int a[])
{
  int i;
  int x = 0;
  for (i = 0; i < N; i++)
  {
    if (a[i] != 0) a[x++] = a[i];
  }
  return x;
}

void
imprimeArrayPrimos (int a[], int stop)
{
  int i;
  for (i = 0; i < stop; i++) {
    printf ("%d ", a[i]);
  }
}

int
main ()
{
  int a[N];
  int stop;
  float sqrtm = sqrt (N);
  unsigned long long somaprim;
  initArray (a);
  // assume-se que 1 nao e' primo
  a[1] = 0;
  sieve (a, 2, sqrtm);
  stop = retiraDesnecessariosArrayPrimos (a);
  imprimeArrayPrimos (a, stop);
  return 0;
}