#include <stdio.h>
#include <math.h>

#define SIZE 2000

char prime[SIZE];

void sieve (void)
{
  int i, max;
  int j;
  
  max = sqrt (SIZE);

  prime[0] = 0;
  prime[1] = 0;

  for (i = 2; i < SIZE; i ++)
    prime[i] = 1;

  for (i = 2; i < max; i ++)
    {
      if (prime[i] == 1)
        for (j = i + i; j < SIZE; j += i) /* começa no próximo multiplo de i
                                             saltando de i em i */
          prime[i] = 0;
    }
}

int main(void)
{
    sieve();
    
    int b;
    for(b = 0; b < 20; b++) printf("%d %d\n", b, prime[b]);

    return 0;
}