#include <stdio.h>
#define N 10000000
#define TRUE 1
#define FALSE 0

int main(int argc, char **argv )
{
  char host[80];
  int *a;
  int i, k;
  int found;

  a = (int *) malloc((N+1) * sizeof(int));
  // 1. create a list of natural numbers 2, 3, 4, ... none of which is marked.
  for (i=2;i<=N;i++) a[i] = 1;
  // 2. Set k = 2, the first unmarked number on the list.
  k = 2;
  // 3. Repeat
  while (k*k <= N)
    {
      // a. Mark all multiples of k between k^2 and N
      for (i=k*k; i<=N; i++)
        {
          if ( (i % k) == 0 ) { a[i] = 0; }
        }
      // b. Find the smallest number greater than k that is unmarked 
      //    and set k to this new value until k^2 > N
      found = FALSE;
      for (i=k+1;!found;i++)
      {
        if (a[i]){ k = i; found = TRUE; }
      }
    }
  // 4. The unmarked numbers are primes
  for (i=2;i<=N;i++) { if( a[i] ) { printf("%d\n",i); } }
}